<style> .reveal p{text-align:left;}</style> [YBTJ1268 【例9.12】完全背包问题](http://39.99.183.126:8888/p/YBTJ1268) --- ## 1、完全背包问题 有一个容量为V的背包和N种物品，第i种物品的体积是c[i]，价值是w[i]。每种物品都有无限件可用，求将哪些物品装入背包使得价值总和最大。 --- ## 2、状态转移方程 对于第i件物品，01背包的关键在于取或不取，而完全背包就有取0件、1件、...k件（k<=v/c[i]）的选择，因此状态方程为： ```c++ dp[i][j] = max(dp[i-1][j-k*c[i]] + k*w[i]), 0<=k<=j/c[i] ``` --- ## 简单优化 状态转移方程如下： $$ dp_{i,j}=\max_{k=0}^{+\infty}(dp_{i-1,j-k\times w_i}+v_i\times k) $$ 考虑做一个简单的优化。可以发现，对于 $dp_{i,j}$，只要通过 $dp_{i,j-w_i}$ 转移就可以了。因此状态转移方程为： $$ dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-w_i}+v_i) $$ 理由是当我们这样转移时，$dp_{i,j-w_i}$ 已经由 $dp_{i,j-2\times w_i}$ 更新过，那么 $dp_{i,j-w_i}$ 就是充分考虑了第 $i$ 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。 --- ## 3、物品拆分 把第i件物品拆分成多个物品，体积为c[i]*2^k，价值为w[i]*2^k，其中k满足c[i]*2^k<=v，这样，完全背包问题就转化成了01背包问题，即每个物品只能选或者不选。 --- 这样拆分的依据：对于第i件物品，不管选择几件，都可以用若干个2^k的和。例如： ``` 0 = 都不选 1 = 2^0 2 = 2^1 3 = 2^1 + 2^0 ``` --- ## 4、一维状态 类似01背包的一维状态，区别在于内层循环（容量）为正向c[i]..v。 ``` for 1..n for c[i] .. v dp[j]=max(dp[j], dp[j-c[i]]+w[i]) ``` --- ## 5、装满问题 如果题目要求“恰好装满”，和01背包一样，只需要把除dp[0][0]外的其它dp[0][j]都初始化为-inf即可。 在某个状态计算时，假如装不满的结果是-inf，当计算max时，就会被淘汰出去。