完全背包问题¶
问题描述¶
有 \(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]);