背景知识: 动态规划 @算法导论 p243
题目
某旅行者外出, 需要将5件物品装入包中. 包的总容量是12kg, 物品重量及价值如表. 问如何装这些物品, 才能使得总价值最大? (写出递归式, 列表计算, 算法).
| item | A | B | C | D | E |
|---|---|---|---|---|---|
| weight | 11 | 5 | 4 | 3 | 1 |
| value | 8 | 4 | 3 | 2 | 0.5 |
解答
(1) Optimal Substructure
对某个物品来说, 无论取或者不取, 余下容量的装填都应该是最优的.
(2) Recurrence Equation
在决策第i个物品的决策时, i~j物品的价值总和S有:
S(i, j, Cap) = max{ S(i-1, j, Cap-w[i])+v[i], S(i-1, j, Cap)},
其中, Cap表示剩余容量Capacity;
注意到j实际上是固定的值, 即j=n, 所以可以简化成:
S(i, Cap) = max{ S(i-1, Cap-w[i])+v[i], S(i-1, Cap) }
考虑边界情况,
a. 当w[i] > Cap时, 物品已经超出容量, 因此:
S(i, Cap) = S(i-1, Cap)
b. 当i>j, 或者Cap = 0时,
S(i, Cap) = 0
(3) Bottom-up Tabular Calculation
- 表格计算
tabular calculation.png
(4) Algorithm
knap(n, w[1~n], W)
#init
let S be a new table, rec be an array
for cap = 0~W: #i > j
S[6][cap] = 0
for i = 1~n+1: #cap = 0
S[i][0] = 0
#calculation
for i = n~1:
for cap = 0~W:
rec[i] = 0 #item[i] out by default
if w[i] <= cap: #weight OK
if S[i-1][cap-w[i]]+v[i] > S[i-1][cap]:
S[i][cap] = S[i-1][cap-w[i]]+v[i]
rec[i] = 1 #item[i] in
else:
S[i][cap] = S[i-1][cap]
else: #too weighty
S[i][cap] = S[i-1][cap]
return S, rec
