有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
分析
思路和01背包问题差不多,但是多了一个维度,就是关于存放物品个数的这个维度
对比01背包问题
1 | f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); |
为了实现多个物品的对比,所以上式可以写为
1 | f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i]+···f[i-1][j-n*w[i]]+n*w[i]); |
如此来说也就意味着我们要写三重循环,这显然是会超时的。为了优化他,我们开始对他进行推导
1 | f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2*v]+w+···+f[i-1][j-n*v]+(n-1)*w); |
我们发现下面这个式子,只需要在后面加上一个w就可以得到与
1 | f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i]+···f[i-1][j-n*w[i]]+n*w[i] |
相同的式子。我们进行代换可得
1 | f[i][j]=max(f[i-1][j],f[i][j-v]+w); |
这就是完全背包问题的状态转移方程
代码
1 | #include <iostream> |
优化
我们尝试将这个状态转移方程优化成一维。经过对比发现仅仅是删掉一维后方程仍然保持正确
1 | #include <iostream> |
对比
01背包问题在第二维是从后往前做的,而完全背包问题是从前往后做的,这其实取决于他们的一维形式,01要求的是f[i-1][],而完全经过优化后是f[i][],是和前一项息息相关的。所以才会造成两个问题的优化版本做法不同的问题。
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/10/%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
![]()