概述
上一篇博客讲到了背包问题中的01背包问题,今天这篇博客继续介绍背包问题中的完全背包问题。
首先回顾一下背包问题,背包问题解决的是:一共有N
件物品,有一个容积为V
的背包,第i
个物品有两个属性:体积v[i]
和价值w[i]
,在背包能装下的前提下,能装的物品最大价值是多少。
完全背包
完全背包问题的关键是,每个物品有无限个。
状态转移方程
根据上次求解01背包的思路,求解完全背包也需要分成两个部分,分别是状态表示和状态计算。
所有背包问题的二维状态表示都和01背包问题一样:用f[i, j]
表示所有只考虑前i
个物品,且总体积不大于j
的所有选法。以下的多重背包,和分组背包问题的状态表示将不再赘述。
而完全背包问题的状态计算也可以参考01背包问题。01背包问题是将状态分成了两份,分别是不含i
和含i
的部分。因此01背包问题的状态转移方程为:f[i, j] = Max(f[i - 1, j], f[i-1, j-vi]+wi)
而完全背包有无限个物品,那么我们可以将状态分成无限份,我们用k
来表示第k
个状态的计算,那么k=0
就表示不含i
的情况,f[i, j] = f[i - 1, j]
。
而后面的含有1个
,含有两个
,…,一直到含有无限个
的状态,我们来计算第k
个状态来表示。和01背包相似的,01背包计算含i
的状态是通过减去第i
个物品的体积的状态,加上第i
个物品的价值得到的。
那么求第k
个状态就可以先去掉k
个物品i
,求Max,再加回来k
个物品i
的价值。
综上,得到完全背包的状态表示为:f[i, j] = Max(f[i-1, j-v[i]*k] + w[i]*k) (k表示枚举的第i个物品的个数)
。
朴素代码实现
根据状态转移方程可以写出完全背包问题的朴素实现代码,如下。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
for (int k = 0; k * v[i] <= j; k ++) {
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[m];
return 0;
}
完全背包问题的优化
根据上面的代码可以看出完全背包问题套了三层循环,时间复杂度还是比较大的。
我们可以根据完全背包的状态转移方程来给代码进行优化。状态转移方程现在计算的是k
从0枚举到i
的情况,展开来可以写成下面的样子:
f[i, j] = Max(f[i-1, j], f[i-1, j-v]+w, f[i-1, j-2v]+2w, f[i-1, j-3v]+3w, ...])
而f[i, j-v]
的状态计算展开如下:
f[i, j-v] = Max( f[i-1, j-v], f[i-1, j-2v]+2w, f[i-1, j-3v]+3w, ...])
对比上下两式,可以发现f[i, j]
除了k=0
的情况,后面的状态可以用f[i, j-v]+w
表示,这样计算完全背包问题的状态时,就不必从k=1
一直计算到无限的状态了,只需要用第i
层的状态减去一件物品的体积,再加上一件物品的价值即可得出。(上图也有计算步骤)
因此代码可以优化如下。
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
}
同理根据01背包的二维优化到一维的方法,可以再将二维数组,优化到一维,不过和01背包问题不同的是,完全背包的最大值函数里,是用第i
层的状态,因此不需要j
从大到小遍历循环,直接从v[i]
遍历到m
即可。
优化后的代码如下.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++) {
for (int j = v[i]; j <= m; j ++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m];
return 0;
}
近况碎碎念
虽然蓝桥杯刚结束吧,但是最近事情还是有点多,又忙着考研的同时用闲暇时间写写博客也是很惬意的。
背包问题未完待续…
版权声明:本文为博主作者:DarkComxEating原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/DarkComxEating/article/details/137746871