演算法›Ch3 動態規劃第 14 題/共 40 題
14. 0/1 Knapsack、Dynamic Programming、遞迴式
#AL-03-014易0/1 KnapsackDynamic Programming遞迴式
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 only choose to take or leave each entire item. Let denote the highest total value you can obtain with items and a knapsack of weight capacity . Which of the following recurrence relations is correct?
📄 台大110
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃