演算法›Ch7 貪婪演算法第 1 題／共 12 題
1. Fractional Knapsack、貪心演算法
#AL-07-001易Fractional Knapsack貪心演算法
Consider a fractional knapsack problem of 6 items. The -th item is worth dollars and weighs pounds.
| item | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| pounds | 4 | 2 | 8 | 5 | 5 | 8 |
| dollars | 3 | 8 | 16 | 7 | 9 | 20 |
Suppose that at most pounds can be carried in the knapsack. The sequence of picking the items is
參考答案與解析
答案 (A) 2,6,3,5：計算單位重量價值：item1=0.75, item2=4, item3=2, item4=1.4, item5=1.8, item6=2.5。依價值密度由大到小排序：2(4)>6(2.5)>3(2)>5(1.8)>4(1.4)>1(0.75)。依序取用：item2全取(重2,剩18)，item6全取(重8,剩10)，item3全取(重8,剩2)，item5只能取2/5(重2用完)。實際取用到的物品依序是2,6,3,5，對應選項(A)。
📄 台大111
▤完整推導請見《WH 資工筆記 · 演算法》Ch7 貪婪演算法