完全背包问题¶
问题描述¶
有 \(n\) 种 物品（ 每种物品有 无限件 ） 和 一个容量为 \(W\) 的背包，每个物品有重量 \(w_i\) 和价值 \(v_i\) 两种属性，要求：选若干物品放入背包，使背包中物品的 总价值最大 且 背包中物品的总重量不超过背包的容量
状态转移方程¶
状态定义¶
与 0-1 背包完全相同，设 f[i][j] 表示只考虑前 i 个物品时，容量为 j 的背包所能达到的最大总价值
状态转移¶
每种物品可以不选，也可以选一个或多个，但第 i 种物品最多选 W/w[i] 个
考虑对每件物品，枚举其选择件数，得到 状态转移方程 如下：
f[i][j]=max(f[i-1][j-k*w[i]]+k*v[i]) ， 其中 0<=k<=W/w[i]
这样做的时间复杂度为
\[O\Big(\displaystyle W×\sum_{i=1}^n\frac{W}{w_i}\Big)\]
能不能优化呢？
还记得 0-1 背包 的逆序枚举吗？0-1 背包中我们为了防止对一个物品做出多次决策而采用逆序枚举，这启示我们可以用顺序枚举对一个物品做出多次决策！
这样做的状态转移方程如下：
f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i])
对比 0-1 背包的状态转移方程：
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])
发现不同了吗？
只要在 0-1 背包的基础上改一下 j 的枚举顺序即可，代码如下：
for(int i=1;i<=n;i++)
for(int j=0;j<=W;j++)
f[j]=max(f[j],f[j-w[i]]+v[i]);