背包问题

问题

输入：

• 背包容量W
• n个物品：
  • 价值$v_i$
  • 大小$w_i$

输出：
最优解$S \subseteq \lbrace 1,2,3,…,n \rbrace$；
S中的物品在满足大小之和不超过背包容量W的条件下,最大化$\sum_{i\in S}{v_i}$

思路

假设把所有物品排成一列，考虑最后一个物品$n$，价值$v_n$，大小$w_n$:

1. 如果$n \notin S$, 则对于其他$n-1$个物品和容量$W$，$S$也是最优解
2. 如果$n \in S$, 则对于其他$n-1$个物品和容量$W-w_n$，$S-{n}$是最优解

反证：存在$\tilde{S}$是比$S-{n}$更优的解，则$\tilde{S} + {n}$是比$S$更优的解，这与$S$是最优解矛盾

所以在已知去掉最后一个物品的子问题解的情况下，最优解只有两种可能：

1. 子问题（n-1个物品和容量W）的最优解
2. 子问题（n-1个物品和容量$W-w_n$）的最优解，加上最后一个物品的价值$v_n$

假设A[i,x]表示由（前i个物品和容量x）组成的子问题解，可以得到动态规划的递推表达式：
$$A[i,x] = max{A[i-1,x], A[i-1,x-w_i]+v_i }$$

算法

伪代码：

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]