假設某小偷帶了一個 2000 cc 的容器,準備要到某家酒店偷酒。 下列是這家酒店內可偷的酒價格與容量。每樣酒可以用小塑膠袋盛裝, 假設塑膠袋不佔空間,請問小偷要如何偷到總價值最高的酒? (容器可以不裝滿,酒可開瓶分裝)
| 酒名 | 價格 ($) | 每瓶容量 (cc) | 剩餘數量 (瓶) |
|---|---|---|---|
| 白蘭地 Brandy | 1380 | 300 | 2 |
| 葡萄酒 Wine | 2800 | 700 | 2 |
| 威士忌 Whisky | 1400 | 320 | 1 |
| 香檳 Champagne | 1800 | 500 | 5 |
| 台灣陳年高粱 | 600 | 600 | 20 |
因可分裝,所以先計算每種酒每 cc 的價格,再由最高者取捨:
| 酒名 | 價格 ($) | 每瓶容量 (cc) | 每 cc 價格 | 剩餘數量 (瓶) | 總 cc 數 |
|---|---|---|---|---|---|
| 白蘭地 Brandy | 1380 | 300 | 4.6 | 2 | 600 |
| 葡萄酒 Wine | 2800 | 700 | 4.0 | 2 | 2800 |
| 威士忌 Whisky | 1400 | 320 | 4.375 | 1 | 320 |
| 香檳 Champagne | 1800 | 500 | 3.6 | 5 | 2500 |
| 台灣陳年高粱 | 600 | 600 | 1.0 | 20 | 12000 |
結論:
白蘭地 (600 cc) + 威士忌 (320 cc) + 葡萄酒 (1080 cc) = 2000 cc
總價值:
4.6 × 600 + 4.375 × 320 + 4 × 1080 = 8480 $(平均 4.2 $/cc)
由此可知:可分割物品使用貪婪法即可解決,不需要特別高深的演算法。