输入:
- 背包容量W
- n个物品:
- 价值$v_i$
- 大小$w_i$
输出: 最优解$S$,$S\subseteq {1,2,3,...,n}$; S在满足$\sum_{i\in S}{w_i} <= W$的条件下,最大化$\sum_{i\in S}{v_i}$
假设把所有物品排成一列,考虑最后一个物品$n$,价值$v_n$,大小$w_n$:
- 如果$n \notin S$, 则对于其他$n-1$个物品和容量$W$,$S$也是最优解
- 如果$n \in S$, 则对于其他$n-1$个物品和容量$W-w_n$,$S-{n}$是最优解
反证:存在$\tilde{S}$是比$S-{n}$更优的解,则$\tilde{S} + {n}$是比$S$更优的解,这与$S$是最优解矛盾
所以在已知去掉最后一个物品的子问题解的情况下,最优解只有两种可能:
- 子问题(n-1个物品和容量W)的最优解
- 子问题(n-1个物品和容量$W-w_n$)的最优解,加上最后一个物品的价值$v_n$
假设A[i,x]表示由(前i个物品和容量x)组成的子问题解,可以得到动态规划的递推表达式:
伪代码:
let A = 2-D array
initialize A[0,x] = 0 for x = 0,1,2,...,w
for i = 1,2,3,...,n:
for x = 0,1,2,...,w:
A[i,x] := max{A[i-1,x], A[i-1,x-w] + v}
return A[n,w]