演算法›Ch7 貪婪演算法第 3 題／共 12 題
3. Fractional Knapsack、貪心演算法
#AL-07-003易Fractional Knapsack貪心演算法
Consider the following six items with their weights and values. Suppose you have a knapsack with a maximum weight capacity of 10.
| Item | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Weight () | 2 | 1 | 4 | 5 | 2 | 10 |
| Value () | 10 | 6 | 28 | 50 | 10 | 80 |
Suppose you can take any arbitrary portion of each item. What is the highest total value you can get by filling your knapsack? A. 184 B. 100 C. 90 D. 84
參考答案與解析
答案 (C) 90。單位重量價值：item1=5,item2=6,item3=7,item4=10,item5=5,item6=8。依價值密度排序：4(10)>6(8)>3(7)>2(6)>1=5(5)。取item4全部(重5,價值50,剩5容量)，接著item6只能取一半(重5/10,價值80×0.5=40)。總價值=50+40=90。
📄 台大110
▤完整推導請見《WH 資工筆記 · 演算法》Ch7 貪婪演算法