none
判斷大小的語法(最佳組合程式的寫法) RRS feed

  • 問題

  • 題目:百貨公司選購促銷商品的最佳組合
    說明:某百貨公司推出福箱活動,每人可購買一個福箱來裝這次活動特價區的限量商品,每件商品不限制購買數量,但總重量不得超過50KG(箱體重量不計)。某位精打細算的媽媽想利用這次的活動來選購最值錢的商品,在不超重的狀況下
    (商品總重量小於等於50KG),請問這位媽媽應該如何去選取最值錢的商品組合?請將最佳組合的商品細目列出。

    這是我自己上網找的題目,想要練習...
    如果這是數學題已經解決了,偏偏這是程式題。

    商品         價格       重量(KG)  平均價格
    運動套裝    3090        3          
    1030               
    名牌大衣    4580        4          1145
    名牌床包組 7999        7         
    1142.714 
    鍋具組       5688        5          1137.6
    杯具組       2599        3         
    866.3333
    運動球鞋    1590        2          795


    我一開始是想說要是選最佳組合,必定是挑單價最高的,因為我將每個價格都除上重量,
    得到了上面的平均價格,單價最高的昰名牌大衣,但很明顯的50KG無法整除4KG,
    因此,它一定會跟其他商品作搭配,得到[最佳組合],我算了算,找到了9件名牌大衣+2個名牌床包組,應該會是最佳組合,加起來剛剛好是50,又剛好是單價最高跟單價第二(9*4+7*2),不確定有沒有計算錯誤,但這不是重點,重點是我想要用程式判斷哪個平均價格最高,而不是用肉眼判斷,判斷出來以後,還是不太會寫,不知道要怎樣才能求出
    "9件名牌大衣+2個名牌床包組",因此總共問題有兩個。


    1.如何用程式判斷"變數"的大小(我把平均價格設a b c d f g)。
    2.如何求出正解為"9件名牌大衣+2個名牌床包組"。
    我有自己先嘗試過了,真的不會才來求助的,希望大家幫忙

    2013年2月10日 上午 07:26

解答

  • 用 背包問題(knapsack problem) 來解 (http://zh.wikipedia.org/wiki/背包問題 ), 因為沒有限制各物品的取用數量, 所以應該是 "無界背包問題".

    關鍵字 : 遞迴 (recursive), 動態規劃 (Dynamic programming)

    參考 wiki 的說明摘要 : 背包的最大價值在 "將要放進去的東西的價值" 加上 "已放進背包內的東西的總最大價值", 而且總重量不超過或等於所限定的值

    依照這個概念, 使用 遞迴 加上 動態規劃 儲存已算出的值, 以減少 遞迴 所需的時間. 然後列舉出 1~50kg, 每一公斤可以怎麼放東西來求得背包的最大價值

    t_dict = {u'運動套裝' : (3090, 3),
              u'名牌大衣' : (4580, 4),
              u'名牌床包' : (7999, 7),
              u'鍋具組  ' : (5688, 5),
              u'杯具組  ' : (2599, 3),
              u'運動球鞋' : (1593, 2)}
    
    # Dynamic Programming : 記錄已算過的
    now_dict = {0 : [0, []],}
    
    # max bag conpacity
    max_kg = 50
    
    def ukp() :
        ''' 無界背包問題 '''
        for i in range(max_kg+1) :
            refunc(i)
    
        for j in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50) :
            print '%3dkg total price : %5d,' % (j, now_dict[j][0]),
            print '\titems : ',
            for k in now_dict[j][1] :
                print k.encode('cp950'),
            print
    
    
    def refunc(kg) :
        ''' recursive '''
        try :
            # minumn is 0
            if kg < 0 :
                kg = 0
            return now_dict[kg]
    
        except KeyError :
            # not exist in now_dict, calculate here
            temp_price = 0
            max_now = 0
            itemlist = []
            # test each item one by one
            for i in t_dict.keys() :
                # check item weight
                i_kg = t_dict[i][1]
                if i_kg > kg :
                    continue
    
                # recursive here
                price, templist = refunc(kg-i_kg)
                temp_price = t_dict[i][0] + price
                # determine the max price
                if temp_price > max_now :
                    max_now = temp_price
                    itemlist[:] = templist
                    itemlist.append(i)
    
            # record into now_dict
            now_dict[kg] = [0, []]
            now_dict[kg][0] = max_now
            now_dict[kg][1][:] = itemlist

    結果

      1kg total price :     0,      items :
      2kg total price :  1593,      items :  運動球鞋
      3kg total price :  3090,      items :  運動套裝
      4kg total price :  4580,      items :  名牌大衣
      5kg total price :  5688,      items :  鍋具組
      6kg total price :  6180,      items :  運動套裝 運動套裝
      7kg total price :  7999,      items :  名牌床包
      8kg total price :  9160,      items :  名牌大衣 名牌大衣
      9kg total price : 10268,      items :  名牌大衣 鍋具組
     10kg total price : 11376,      items :  鍋具組   鍋具組
     20kg total price : 22900,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣
     30kg total price : 34318,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌床包 名牌床包
     40kg total price : 45800,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣
     50kg total price : 57218,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌床包 名牌床包

    以上是 python 的語法, 供你參考, 不過你要有的是 觀念, 概念, 用什麼語法都沒差, 因為你的想法還是不會變, 只是套進不同的語句裡而已, 所以不要覺得你找的程式碼都看不懂, 你把它一行一行拆, 不就是老師教你的, 書上寫的那些 基本語句 兜出來的嗎. 以上希望對你有幫助.

    以上有誤的話, 希望大家指教. 謝謝~

    by the way, 你這題用 數學 怎麼解呀 ??

    2013年2月16日 下午 03:18

所有回覆

  • 你的努力在哪裡?


    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月10日 上午 08:17
    版主
  • 您是指我自己所練習寫的程式碼?
    您說:學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。
    我想知道那如果我遇到我不會的語法,用學校的課本整本翻閱也找不到我想知道的東西,
    而上網搜尋時,又不知道關鍵字應該打些什麼
    (畢竟是沒遇過的語法,如果是if,for,已經知道的,記起來不是難事,但我連需要運用到哪些語法時都不知道,我該從何查起?)
    這時你昰怎麼解決的,還是您根本沒遇過我這種情形...
    或是你好不容易找到網路上有人有跟你差不多的問題,結果回覆昰一長串沒有附註明的程式碼,你複製貼上能達到你要的效果,
    卻是什麼都沒學習到,根本毫無意義,但別人回答問題已經昰很好了,總不可能要求別人在多跟你說些什麼,
    他們不是我的奴隸,那麼我該如何去實現你所說的那句話?
    我該去問誰,或是我該去買什麼書來參考來練習來進步?
    您又是如何進步的呢?

    2013年2月10日 上午 08:41
  • 當然...

    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月10日 上午 08:48
    版主
  • 如果你只想著 "用你想用的程式碼" 的思維去看每一本書,我可以保證你要花幾百倍的時間去看一大堆書。例如你只會用 C#,卻問說 "如何用 C# 寫 Device Driver",我可以保證你絕對找不到任何一本書;又如你只會用 C#,卻問說 "如何用 C# 去讀寫硬體",中文書有寫這個的用五根手指數還太多。

    或許學校的課本或指定用書沒有 cover 到你想要的,而其他的書有但卻是 C++ 的,請問你要看還是不看?

    看書要學的是作者透過文宇要傳達的概念,範例程式碼也只是要傳達概念的一種工具,模擬作者的範例寫出自己的程式則是要把作者傳達的概念吸收進來變成自己的,可是如果因為程式語言的不同就拒絕閱讀,那豈不可惜嗎? 

    你自己也說了:"我有自己先嘗試過了,真的不會才來求助的,希望大家幫忙 "

    網友不是你肚子裡的蛔蟲,誰曉得你看了什麼? 哪裡不會? 是 key point 不會還是整個都不會? 你不說誰知道?

    關鍵字搜尋的能力是要自我訓練的,我自己也訓練了好幾年才有 "看到問題就知道要查詢什麼關鍵字" 的能力,而且也還是會出錯,但關鍵字抓錯不但可以隨時修正,而且也幾乎不會有出錯的成本,是最佳的自我能力訓練之一,簡單的說就是:查就對了,查錯就換個字再查就好。


    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月10日 上午 09:59
    版主
  • 我文中有敘述到,我不會的地方昰在比大小的部分...
    就是我知道從平均價格下手(我的想法),但是不知道怎麼把平均價格作排序,
    也不知道如何將平均價格的1跟2湊成50KG,這我文中都有提到...

    我只是想要至少能看懂程式碼在寫什麼,如果是C++,那就C++,只要有註解的都可以(但是沒人會幫我註解吧...)
    我困擾的就是沒人註解,那麼我該如何去知道他的意義,連買書查都不知道買哪本 :(

    自己寫的程式碼有格式規定嗎,或是直接複製貼上??

    2013年2月10日 下午 03:15
  • 冷夜兄好:

    您的平均價格解法原則上是不正確的.

    這個問題其實很難@@, 是演算法中很有名的"小偷背包"問題

    請參閱

    http://en.wikipedia.org/wiki/Knapsack_problem

    • 已提議為解答 Alex_Lee 2013年2月15日 上午 09:35
    2013年2月10日 下午 03:27
  • (題外話)
    暫且先不論你使用的解法是否是正確的解法~(因為我不曉得)

    但是或許往後再問問題的時候,你可以更精確的附加說明說如何做平均價格的排序

    如果今天先把你回應理問題來解釋的話
    1. 如何把平均價格做排序
        以程式的來看的話,簡單的話就是直接把全部的數字丟到一個List,就可以利用sort做排序,
        或是把整個商品自訂成Class (所以Class 包含 名稱、價格、重量),放到List就可以去做排序的動作,
        此部分請參考
        List<T> 方法 (如果你今天是要學習的話,建議請先閱讀過MSDN的文件後,再去看其他人寫的網誌或範例)
        http://msdn.microsoft.com/zh-tw/library/b0zbh7b6.aspx
        http://www.dotblogs.com.tw/timchang/archive/2012/10/24/78823.aspx

    2.把平均價格的1跟2湊成50KG
       這部分的話,或許你先可以換個思考方式來想,拋棄掉一些先入為主的觀念,
       利用比較原始比較笨的方式來看
       簡單的說,就是像以排列組合的思考方式,把全部的可能性列出來,
       然後把每個可能性都去做計算,最後在比較大小,取出最大的數字後就是你的答案,
       當然...人這樣列會列到死,但以程式來看的話,
       你可以用迴圈的方式來排列出來各種的結果,在迴圈裏面就可以計算結果放置到某個物件裡,
       最後再取最大值即可。
       (並且可以研究.Net 的功能來幫助你不要減少使用迴圈的機會來完成,但這就是建議在你已經先有最初版的程式後,再去做後續的研究調整與修改)
       中間你要怎樣撰寫程式就沒有唯一的解法了,
       我知道這個方法是最笨的思考方法,而這個方法是建構在並不知道有甚麼演算法的方式,
       如果你已經知道有何演算法是可以解決這樣的問題的話,
       那就把演算法轉換成程式邏輯即可。
       前提是你要先確定這樣的演算法是正確的思考邏輯才可以。


        第二點只是個我想到的可以參考的建議方向而已,不代表是解法唷!
    • 已編輯 Bruce_柏 2013年2月10日 下午 04:56
    2013年2月10日 下午 04:55
  • 您可以參考Greedy Algorithm的解法, 例如:Greedy Algorithms and Maximum Clique

    2013年2月11日 上午 03:16
  • using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Windows.Forms;

    namespace WindowsFormsApplication1
    {
        public partial class Form1 : Form
        {
            float[] f = new float[6];
            float[] m = new float[6];
            int count = 50;
            int q, w, a, r, t, y;
            int g,z=0;
            public Form1()
            {
                InitializeComponent();
            }

            private void Form1_Load(object sender, EventArgs e)
            {
                textBox1.Text = "運動套裝";
                textBox2.Text = "名牌大衣";
                textBox3.Text = "名牌床包組";
                textBox4.Text = "鍋具組";
                textBox5.Text = "杯具組";
                textBox6.Text = "運動球鞋";

                textBox7.Text = "3090";
                textBox8.Text = "4580";
                textBox9.Text = "7999";
                textBox10.Text = "5688";
                textBox11.Text = "2599";
                textBox12.Text = "1590";

                textBox13.Text = "3";
                textBox14.Text = "4";
                textBox15.Text = "7";
                textBox16.Text = "5";
                textBox17.Text = "3";
                textBox18.Text = "2";

                textBox19.Text = "50";

            }

            private void button1_Click(object sender, EventArgs e)
            {
                q = int.Parse(textBox13.Text);
                w = int.Parse(textBox14.Text);
                a = int.Parse(textBox15.Text);
                r = int.Parse(textBox16.Text);
                t = int.Parse(textBox17.Text);
                y = int.Parse(textBox18.Text);


                f[0] = float.Parse(textBox7.Text) / float.Parse(textBox13.Text);
                f[1] = float.Parse(textBox8.Text) / float.Parse(textBox14.Text);
                f[2] = float.Parse(textBox9.Text) / float.Parse(textBox15.Text);
                f[3] = float.Parse(textBox10.Text) / float.Parse(textBox16.Text);
                f[4] = float.Parse(textBox11.Text) / float.Parse(textBox17.Text);
                f[5] = float.Parse(textBox12.Text) / float.Parse(textBox18.Text);
                Array.Copy(f, m, 6);
                Array.Sort(m);
                Array.Reverse(m);
                textBox20.Text = m[0].ToString() + "\r\n" + m[1].ToString() + "\r\n" + m[2].ToString() + "\r\n" + m[3].ToString() + "\r\n" + m[4].ToString() + "\r\n" + m[5].ToString();

                if (m[0] == f[0])
                {
                    g = q;
                }

                else if (m[0] == f[1])
                {
                    g = w;
                }

                else if (m[0] == f[2])
                {
                    g = a;
                }

                else if (m[0] == f[3])
                {
                    g = r;
                }

                else if (m[0] == f[4])
                {
                    g = t;
                }

                else if (m[0] == f[5])
                {
                    g = y;
                }


                while (count >= g)
                {
                    count = count - g;
                    z =z+ 1;

                }

                numericUpDown1.Value = count;
                numericUpDown2.Value = z;
            }



        }
    }

                
    2013年2月11日 下午 02:00
  • 上面是我自己寫的,可能有很多該省沒省的程式碼,
    因為這不是完成品,只是我在思考我的方法而已,
    結果方法有錯,所以沒繼續寫下去了,
    這幾天邊問大家自己還是邊在思考,我先簡單敘述一下我在寫什麼。

    我先把平均價格的高低分出來,結果昰"名牌大衣"的平均價格(價格/KG)最高,
    我用陣列的方式求出,接著我在求出"名牌大衣"的重量,
    開始用50KG減,減到50KG(count)<g就停止,
    接著再將count減減看平均價格第二名的,第三名的,第四名的等等...
    如果有東西能減,就減,如果沒有,就代表這已經是最佳組合了,
    結果我在寫的時候發現,我會減掉12個名牌大衣的重量,省下2KG,只能放運動球鞋。
    所以我總共免費獲得12*4580+1590=56550元,
    可昰如果我選9件名牌大衣,跟2個名牌床包組,我可以免費獲得4580*9+7999*2=57218元,
    很明顯的我的程式碼能寫出的答案是錯誤的,
    接著我又想如果count有機會昰平均價格第二名或是第三名的倍數,就換成減平均價格第二名或第三名的重量,
    但是很明顯的這也是錯誤的,如果剛好是第一名跟第二名的倍數(如果第一名就能整除那幹嘛用到第二名),就會錯誤,
    還有我自己也找到一個例子,就算不是剛好第一名跟第二名的倍數,
    一開始的50開始減,50 46 42,
    到42KG的時候就是7KG的倍數,可昰答案只有4580*2+7999*6=57154,依然比57218還要小,所以我這個想法還是錯誤。
    不停的思考結果還是想不出什麼好方法能配對出9件+2組,9跟2這兩個數字不知道從哪變出來 :(

    如果看不懂我再說啥歡迎詢問,我會盡全力說到你懂 :)


    2013年2月11日 下午 02:15
  • http://sriwantha.blogspot.tw/2011/07/knapsack-problem-in-c.html


    學習不是查個 Google 套個書上的範例就算了,而是去熟悉了解每個程式碼背後的意義,否則就算學個幾百年,它也不會是你的。

      • 小朱的技術隨手寫:http://www.dotblogs.com.tw/regionbbs/
      • 雲端學堂Facebook: http://www.facebook.com/studyazure

    2013年2月11日 下午 02:20
    版主
  • 如果你們有教整數規劃,這是整數規劃基本題。

    以最佳組合來說,少了一個重要條件,例如說節省成本。不然你的目標函數列不出來。

    重量跟價值本身沒啥關係,這又不是秤斤賣的東西...

    所以你的最有價值本身要明確定義。


    論壇是網友平等互助 保證解答請至 微軟技術支援服務


    提問時,錯誤情境描述與錯誤訊息很重要,情境描述包含你做了什麼,預期的結果與實際發生的結果。一個最爛的問法範例:「我的電腦電腦怎麼不能開機?」誰知道你家是不是沒電還是你根本找不到電源鈕。

    2013年2月11日 下午 04:09
  • 簡單來說就是限重50KG,你能拿越多錢走越好...
    既然有限重應該跟重量有關係 :O?

    2013年2月12日 上午 06:20
  • 最佳化要定義:

    1. 目標函數

    2. 限制式

    所得的結果是該目標下的最佳解,換個目標或是調整權重時就會改變。

    基本理論會在大學微積分第二章 limit 介紹。

    線性規劃會在線性代數或是工程數學二介紹。整數規劃是線性規劃轉非線性規劃特殊解,一般會先由線性規劃的最佳解起開始做列舉解。


    論壇是網友平等互助 保證解答請至 微軟技術支援服務


    提問時,錯誤情境描述與錯誤訊息很重要,情境描述包含你做了什麼,預期的結果與實際發生的結果。一個最爛的問法範例:「我的電腦電腦怎麼不能開機?」誰知道你家是不是沒電還是你根本找不到電源鈕。

    2013年2月12日 下午 03:25
  • 用 背包問題(knapsack problem) 來解 (http://zh.wikipedia.org/wiki/背包問題 ), 因為沒有限制各物品的取用數量, 所以應該是 "無界背包問題".

    關鍵字 : 遞迴 (recursive), 動態規劃 (Dynamic programming)

    參考 wiki 的說明摘要 : 背包的最大價值在 "將要放進去的東西的價值" 加上 "已放進背包內的東西的總最大價值", 而且總重量不超過或等於所限定的值

    依照這個概念, 使用 遞迴 加上 動態規劃 儲存已算出的值, 以減少 遞迴 所需的時間. 然後列舉出 1~50kg, 每一公斤可以怎麼放東西來求得背包的最大價值

    t_dict = {u'運動套裝' : (3090, 3),
              u'名牌大衣' : (4580, 4),
              u'名牌床包' : (7999, 7),
              u'鍋具組  ' : (5688, 5),
              u'杯具組  ' : (2599, 3),
              u'運動球鞋' : (1593, 2)}
    
    # Dynamic Programming : 記錄已算過的
    now_dict = {0 : [0, []],}
    
    # max bag conpacity
    max_kg = 50
    
    def ukp() :
        ''' 無界背包問題 '''
        for i in range(max_kg+1) :
            refunc(i)
    
        for j in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50) :
            print '%3dkg total price : %5d,' % (j, now_dict[j][0]),
            print '\titems : ',
            for k in now_dict[j][1] :
                print k.encode('cp950'),
            print
    
    
    def refunc(kg) :
        ''' recursive '''
        try :
            # minumn is 0
            if kg < 0 :
                kg = 0
            return now_dict[kg]
    
        except KeyError :
            # not exist in now_dict, calculate here
            temp_price = 0
            max_now = 0
            itemlist = []
            # test each item one by one
            for i in t_dict.keys() :
                # check item weight
                i_kg = t_dict[i][1]
                if i_kg > kg :
                    continue
    
                # recursive here
                price, templist = refunc(kg-i_kg)
                temp_price = t_dict[i][0] + price
                # determine the max price
                if temp_price > max_now :
                    max_now = temp_price
                    itemlist[:] = templist
                    itemlist.append(i)
    
            # record into now_dict
            now_dict[kg] = [0, []]
            now_dict[kg][0] = max_now
            now_dict[kg][1][:] = itemlist

    結果

      1kg total price :     0,      items :
      2kg total price :  1593,      items :  運動球鞋
      3kg total price :  3090,      items :  運動套裝
      4kg total price :  4580,      items :  名牌大衣
      5kg total price :  5688,      items :  鍋具組
      6kg total price :  6180,      items :  運動套裝 運動套裝
      7kg total price :  7999,      items :  名牌床包
      8kg total price :  9160,      items :  名牌大衣 名牌大衣
      9kg total price : 10268,      items :  名牌大衣 鍋具組
     10kg total price : 11376,      items :  鍋具組   鍋具組
     20kg total price : 22900,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣
     30kg total price : 34318,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌床包 名牌床包
     40kg total price : 45800,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣
     50kg total price : 57218,      items :  名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌大衣 名牌床包 名牌床包

    以上是 python 的語法, 供你參考, 不過你要有的是 觀念, 概念, 用什麼語法都沒差, 因為你的想法還是不會變, 只是套進不同的語句裡而已, 所以不要覺得你找的程式碼都看不懂, 你把它一行一行拆, 不就是老師教你的, 書上寫的那些 基本語句 兜出來的嗎. 以上希望對你有幫助.

    以上有誤的話, 希望大家指教. 謝謝~

    by the way, 你這題用 數學 怎麼解呀 ??

    2013年2月16日 下午 03:18