無聊問題

夢想中有個程式應是這樣的:

我輸入我想買的麥當勞食物,例如一個雙層芝士孖堡,一個中薯條,一杯中可樂,一個至尊漢堡。

全部單買的話價錢是

雙層芝士孖堡 12.5 元
至尊漢堡 16.8 元
中薯條 8.8 元
中可樂 8.5 元

總數是 46.6 元。但是我們知道雙層芝士孖堡+中薯條+中可樂是雙層芝士孖堡套餐。至尊漢堡+中薯條+中可樂是至尊漢堡套餐。
雙層芝士孖堡套餐是 23.8 元,至尊漢堡套餐是 26.5 元。
如果買雙層芝士孖堡套餐加至尊漢堡是 23.8 + 16.8 = 40.6 ,如果買至尊漢堡套餐加雙層芝士孖堡是 26.5 + 12.5 = 39 。亦即是選買至尊漢堡套餐加雙層芝士孖堡能省 1.6 元。

這個 program 的目的是要找出最低價的組合。我想這個程式的演算法第一步是找出用戶輸入的食物能夠組成怎樣的不同套餐組合。因為買套餐應在任何時候都比單買便宜。再比較不同組合的價錢。這個我想是最直接的演算法。我在想到底有沒有更好的演算法。1

  1. p.s. 我沒有 CS degree 。 []

Today on history:

  1. 2007:  Wrong in mind(0)
  2. 2007:  如何食西柚之二(1)
  3. 2007:  Open Standard vs Microsoft(3)
  4. 2007:  Poster Presentation(1)
  5. 2005:  Chainsaw has finished searching app with good searching capability. The search item was not found.(0)
  6. 2004:  Minor amendment(0)
  7. 2004:  suck!!!!!!!!!(0)
  8. 2004:  文化調查結果(0)
  9. 2004:  xxx(0)
  10. 2003:  5x pressurized(0)
  11. 2002:  Grand Prix(0)
  12. 2002:  Periodic(0)

16 thoughts on “無聊問題

  1. 不過就一餐+一包呢個case,我平時係咁計:

    if (set A – set B) < (burger A – burger B)
    then buy set A & burger B
    else buy set B & burger A

    P.S. 我覺得我一樣無聊

  2. 如果每件貨品的數量只得一件的話還好,package 內貨品數多於一件的話 (例如麥記的餐改為一個包 + 兩杯汽水) 的話就會難計得多。簡單來說就要找出共通的最大餐數。

  3. 唔無聊喎。我都會計架,例如買咖啡粉+coffee cream+sugar,不過太複雜,通常只算咖啡粉,因為只飲一個牌子,易計。coffee cream 就難d,多choice,試過兩個牌子一齊計,發現只要買60個的話,兩者每個價錢係一樣。

  4. 第一, 睇下要買幾多中薯條, 幾多中可樂, 幾多個可變餐的包. 求三數最少值, 便知要買多少個餐. (先假設無大薯條, 大可樂)
    第二, 計出所有包的「變餐蝕底價」. (e.g. 至尊漢堡:26.5-16.8=9.8, 雙層芝士孖堡:23.8-12.5=11.3)
    第三, 「蝕底價」越低的包, 越要用餐買.
    完.

    如果計埋大薯條, 大可樂, 其實都不大影響此算法. 因為所有餐變大加的錢都是一樣的. 它們只影響你可以買到幾多個加大餐.

    (我假設咗唔買兒童餐)

    更賤(generic)的解, 明天響我自己度再寫(有時間的話).

  5. >我想這個程式的演算法第一步是找出用戶輸入的食物能夠組成怎樣的不同套餐組合。因為買套餐應在任何時候都比單買便宜。再比較不同組合的價錢。

    唔無聊,比起讀書時做既功課有趣得多。

    暫時我諗倒你呢個係最合理既方法,需要比較既組合較少<當然買得多,組合就幾何級數咁上>,因為咁多種購買組合內無一個趨勢或者模式會平 d ,一定要比較所有組合先得出魚柳包套餐加豬柳蛋包抵 d 定係調轉抵 d ,所以貪婪算法應該未必可以搵出最平組合。

    針對如果要購買既物品太多而比較時間過長,我諗可能要將某 d 組合<例﹕ a+b+c, d+e+f >預先搵左最佳既購買方式儲係資料庫,當遇到物品太多既時候,就將佢拆散一組組黎換算﹕

    a+b+c+c+d+d+e+f+a+b+c
    =(a+b+c)+c+(d+e+f)+(a+b+c)

    咁都唔一定係最平,但快左好多,不過如果種類太多或者每間麥記價錢都有出入就唔掂勒。

  6. 呀, 尋晚心急得滯, 唔記得解釋咩叫「蝕底價」.
    其實我跳咗step.
    至尊漢堡餐26.5, 因為薯條和可樂是百搭, 所以買餐一定有佢地份.
    我地可以假設每件食品在餐入面也有其價值.
    為方便計算, 就假設薯條和可樂在餐入面的價值和單買是一樣的.

    然後, 至尊漢堡餐入面個包的價值就會是26.5-8.8-8.5=9.2 (比單售16.8平了7.6)
    雙層芝士孖堡就是23.8-8.8-8.5=6.5 (比單售12.5平了6.0)
    (註:7.6-6.0=1.6, 這亦是”至尊漢堡套餐加雙層芝士孖堡能省 1.6 元”的原因)

    這就是說, 無論你買甚麼, “至尊漢堡餐抵過雙層芝士孖堡餐”這「真理」是不變的.
    就算你改變薯條和可樂的假設值, 「真理」也不會變.

    不過, 我昨晚把薯條和可樂的價值, 假設為0. 才會出現「蝕底價」這怪東西.

    實際應用嘛, 其實第二步可以一早計好, 記熟次序, 如:
    1(號餐) 抵過 4 抵過 6 抵過 7 …… (我亂寫的)

    咁, 就可即時數到(唔係計到)要咩餐會最平. (連Program都唔洗寫.)

  7. 我昨晚再想亦得出軒爸的解法,最簡單快趣。

    其實無須知道所有組合再計差價,因為能組成餐的只有 8 款食物,只要計每款食物的 delta (餐價 – 單價) ,delta 越細,一定係用嚟買餐最抵。

    假設有齊價錢,只要用 ascending order 嚟排個delta, e.g.

    D3,D5,D2,D1,D4,D6,D8,D7
    (Dn = Delta of the set n)

    只要跟住次序去盡買餐,其餘單買,就是最平的價錢。

  8. As pointed out by the others in the previous postings, ranking the prices of the combos is equivalent to ranking the prices of the combos’ main items, so it’s a trivial problem.

    In the general case where not all combos have the same number of main items, the problem is an “integer programming problem”. Its solution can be found in any textbook on Operations Research.

  9. 很多時寫 program 都是用最直觀的方法,先寫好一個可以 work 的 solution,然後再不停 refactor (當然有 automated test 做安全網更好),未必會即時構想怎去演算法

  10. 如 “The suffocated” 所說,這可以 model 成 Linear Programming 問題去解決,不過通常實際上都會當成 searching 問題,因為易些明白啊

  11. Pingback: 為老不專

Comments are closed.