背包問題(Knapsack Problem)

可分割物品之解決方案

假設某小偷帶了一個 2000 cc 的容器,準備要到某家酒店偷酒。 下列是這家酒店內可偷的酒價格與容量。每樣酒可以用小塑膠袋盛裝, 假設塑膠袋不佔空間,請問小偷要如何偷到總價值最高的酒? (容器可以不裝滿,酒可開瓶分裝)

酒名 價格 ($) 每瓶容量 (cc) 剩餘數量 (瓶)
白蘭地 Brandy13803002
葡萄酒 Wine28007002
威士忌 Whisky14003201
香檳 Champagne18005005
台灣陳年高粱60060020

因可分裝,所以先計算每種酒每 cc 的價格,再由最高者取捨:

酒名 價格 ($) 每瓶容量 (cc) 每 cc 價格 剩餘數量 (瓶) 總 cc 數
白蘭地 Brandy13803004.62600
葡萄酒 Wine28007004.022800
威士忌 Whisky14003204.3751320
香檳 Champagne18005003.652500
台灣陳年高粱6006001.02012000

結論:
白蘭地 (600 cc) + 威士忌 (320 cc) + 葡萄酒 (1080 cc) = 2000 cc
總價值:
4.6 × 600 + 4.375 × 320 + 4 × 1080 = 8480 $(平均 4.2 $/cc)

由此可知:可分割物品使用貪婪法即可解決,不需要特別高深的演算法。