香港新浪網 MySinaBlog
« 上一篇 | 下一篇 »
軒爸 | 17th Apr 2009 | 一般 | (2941 Reads)
電鋸問了一個「無聊問題」, 答案已到其blog回覆. Generic的解, 就寫到這裡來.

問題:
首先, 假設某餐廳有m種食品, 亦有n種餐可供選擇. 每個餐可包含2種或以上的食品. 而買餐的價錢, 就會比散買要平.
問題是, 如果要買一堆食品, 要叫那幾個餐(可重覆)加散買那幾個食品, 才是最便宜呢?
(不過, 先剔除一個情況, 就是就算「部份叫餐」比「全散買」有機會買多了食物, 卻仍然平些.)

解:
第1步, 就是由Worst Case開始, 即是「全散買」.
第2步, 就嘗試合成一個餐, 這裡可以出現n個可能.(因為有n種餐)
第3步, 跟據上面的每個可能, 嘗試把餘下的再合成另一個餐. 這裡可以出現nC2個可能.(因為先組合1號餐再組合2號餐, 和先組合2號餐再組合1號餐, 是一樣的.)
然後, 第4, 5, 6 .... 一直做, 直至不能再組合任何餐.
假設做到第6步就完, 就最多可以出現nC5個可能.
最後, 將這nC5(實際情況會少得多)個可能, 都計個總和, 就知那個組合最平.

然而, 按實際的情況, 是可以做不同的optimization,
就如麥當勞情況, 所有餐也是有薯條, 就算中薯條升級做大薯條, 所加的價錢是一樣的.
就是說, 你可以完全當薯條無到, 因為薯條完全唔影響結果. 你只要記住, 如果你要買4包薯條, 你頂多只做到4個餐就夠了.

可做的optimization, 按實際情況, 還可以有更多更多.

 

Google 廣告
最新留言
網誌統計
文章總數:45
留言總數:300
引用總數:14
閱讀總數:247243
總瀏覽數:383920
MySinaBlog 精選文章