完全背包问题
题目 完全背包问题
思路分析
小明期末考试得了全班第一名，妈妈给了他一个背包，可以去超市任意选购，可以选购多种商品，每种商品可以选购多个，但是选择的商品必须都放在背包里。
超市很大，有很多种商品：火腿，雪糕，饼干 ·····。每种商品都摆满了货架。不同商品的体积和价值不同。
在背包能装下的前提下，小明想尽可能带回价值总量高的商品，请问他能带回的商品的最大价值是多少？
这就是完全背包问题。
有 N 种物品和一个背包，每种物品的数量无限。给出了每种物品的体积 v 和价值 w 以及背包的容量 V。
求解 : 背包能装下的前提下，所能获得的最大价值。
例如我们有 4 种物品和一个容量为 5 的背包。
这四种物品对应的体积和价值分别是：
物品一：体积是 1，价值是 2。
物品二：体积是 2，价值是 4。
物品三：体积是 3，价值是 4。
物品四：体积是 4，价值是 5。
我们可以选择把 1 个 物品一 和 1 个 物品四 放入背包，体积是 1 + 4 = 5，没有超过背包容量，价值是 2 + 5 = 7。
我们可以选择把 1 个 物品一 和 2 个 物品二 放入背包，体积是 1 + 2 + 2 = 5，没有超过背包容量，价值是 2
- 4 + 4 = 10。
我们可以选择把 2 个 物品一 和 1 个 物品三 放入背包，体积是 1 + 1 + 3 = 5，没有超过背包容量，价值是 1 + 1 + 4 = 6。
还有其它选法。
我们的目的是，找到能被背包装下的物品的最大价值。
与01不同的是 同一样物品可以选多次
用闫氏dp分析法来看
从三个步骤进行考虑。
步骤一:集合和集合的状态
所谓的集合，就是一些方案的集合。
用 g[i][j] 表示从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。注意：g[i][j] 不是一个数，是一堆数。
例如 g[2][3] 从前 2 种物品中进行选择，且总体积不大于 3 的各个选法获得的价值的集合。
g[2][3] 的可选择方案包括：
方案一：都不选，总价值为 0。
方案二：选 1 件 物品 1，总价值为 2。
方案三：选 2 件物品 1，总价值为 4。
方案四：选 3件 物品 1，总价值为 6。
方案五：选 1 件物品 2，总价值为 4。
方案六：选 1 件物品 2，一件物品 1，总价值为 6。
所以 g[2][3] = {0，2，4，6，4，2}。
i j 取不同的值，对应不同的 g[i][j]，也就是对应不同的集合。
用 f[i][j] 表示从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。
很明显，f[i][j] 就是 g[i][j] 中的最大值。
i j 取不同的值，就对应不同的 f[i][j]。
我们把 f[i][j] 叫做集合的状态。
例如 f[2][3] 表示从前 2 种物品中进行选择，且总体积不大于 3 的获得的最大价值。
f[2][3] = max(g[2][3] ) = max( 0，2，4，6，4，2) = 6。
g[i][j] 的最大值就是 f[i][j]。
如果我们能把所有集合对应的最大值都求出来，即求出了 f[0][0] ~ f[N][V]， f[N][V] 的含义是在前 N 种物品中进行选择，总体积不大于 V 所获得的最大价值，就是我们要找的答案。
注意，我们不需要把各个集合的所有元素都找出来，只需要求出各个集合的最大值，就能找到答案。下面就是如何求出各个集合的最大值。
步骤二：状态计算
g[i][j] 是从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。
f[i][j] 是从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。
f[i][j] 是集合 g[i][j] 的最大值。
所谓的状态计算是指，如何将把 f[i][j] 算出来。
如果把各个集合 g[i][j] 的状态 f[i][j] 求出来， f[N][V] 就是要找的答案。
回想一下 0 1 背包问题。
01 背包问题把 g[i][j]划分成了 A B 两部分，分别求出这两个部分对应的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，就是 f[i][j]。
01 背包根据是否选择第 i 件物品，也就是第 i 件物品选 0 个还是 1 个，把 g[i][j] 划分成了 A B 两部分，分别求出这两个部分的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。
完全背包问题也是根据第 i 件物品的选择数量，把 g[i][j] 划分成不同的部分，分别求出各个部分的最大值，取各个部分最大值中的最大值，就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。
因为每种物品的数量是无限的，根据第 i 种物品的选择数量可以把 g[i][j] 分为这样几部分：
A 部分： 第 i 种物品选 0 件。
B 部分：第 i 件物品选 1 件。
C 部分： 第 i 件物品选 2 件。
X 部分： 第 i 件物品选 x 件。
因为选择物品的总体积不能大于j，所以第 i 件物品最多选 j / vi 向下取整 件。
对于 A 部分：
第 i 件物品选 0 件。
等价于从前 i - 1 种物品中选择商品，且总体积不超过 j 的各个价值的集合，也就是 g[i - 1][j]。
g[i - 1][j] 这个集合中的最大值是 f[i - 1][j] ，所以 A 部分的最大值就是 f[i - 1][j]。
对于 B 部分：
第 i 件物品选 1 件， 1 个 i 物品会占据 vi的背包空间，剩下的背包空间为 j - vi 。
可以从前 i - 1 种物品中，选出总体积小于等于j - vi 的物品放入背包。
从前 i - 1 种物品中，选出总体积小于等于j - vi 的各个方案获得的价值集合为 g[i - 1][j - vi ]，所以 B 部分的元素为 g[i - 1][j - vi ] 中各个元素加上 wi 。
g[i - 1][j - vi ] 中的最大值为 f[i - 1][j - vi ]，所以 B 部分的最大值为 f[i - 1][j - vi ] + wi。
对于 X 部分：
第 i 件物品选 x 件， x 个 i 物品会占据 x * vi 的背包空间，剩下的背包空间为 j - x * vi 。
可以从前 i - 1 种物品中，选出总体积小于等于j - x * vi 的物品放入背包。
从前 i - 1 种物品中，选出总体积小于等于j - x * vivi 的各个方案获得的价值集合为 g[i - 1][j - x * vi ]，
所以 x 部分的元素为 g[i - 1][j - x * vi ] 中各个元素加上 x * wi 。
g[i - 1][j - x * vivi ] 中的最大值为 f[i - 1][j - x * vi ]，
所以 B 部分的最大值为 f[i - 1][j - x * vi ] + x * wi。
例如 g[2][4]。
第二种物品的体积为 2，选择物品的总体积不能超过 4。
所以第二件物品可以选择：0件、1件、2件。
因此 g[2][4] 可以分成以下几部分：
A 部分：第二件物品选 0 件。A 部分的最大值为： f[i - 1][j - 0 * vi] + 0 * wi 。
B 部分：第二件物品选 1 件。B部分的最大值为： f[i - 1][j - 1 * vi ] + 1 * wi 。
C 部分：第二件物品选 2 件。C 部分的最大值为：f[i - 1][j - 2 * vi ] + 2 * wi 。
g[2][4] 中的最大值为 max(A，B，C)。
通过上面分析，我们可以知道，g[i][j] 可以分成若干部分:
A 部分是第 i 种物品选 0 个对应所有选法获的价值的集合，最大值是 f[i - 1][j]。
B 部分是第 i 种物品选 1 个对应所有选法获的价值的集合，最大值是 f[i-1][j - vi] + wi。
X 部分是第 i 种物品选 x 个对应所有选法获的价值的集合，最大值是 f[i - 1][j - x * vi]+x*wi。
所以 g[i][j] 的最大值就是所有子集的最大值中最大的那个，也就是 f[i][j] = max(A, B ，····) 即：
展开式为：
f[i] [j] = max( f[i-1][j] , f[i - 1][j - vi]+w , f[i - 1][j - 2 * vi]
- 2 * w , f[i - 1][j - k * vi ] + k * w , …..) 其中 k <= j / w。
从计算公式可以看出:
f[i][j] 是由 f[i - 1][j - k * vi ] (0 <= k <= j / wi) 和 wi 计算出来的。
f[i][j]的值是可以从前面已经计算出的 f 值求出来。
如果我们能确定 f[i][j] 的一部分初始值，就能通过该公式，一步步计算得出 f[N][V]，也就是我们要找的答案。
步骤三：确定初始值
完全背包问题的有些状态是能够直接确定的。
例如 f[0][0]。
f[0][0] 的含义是:
从前 0 种物品中选择，并且选出的物品总体积小于等于0 时所能得到的最大价值。 总体积小于等于 0，说明一种物品都不能选择。 因此 f[0][0] = 0。同理 f[1][0] = 0，f[2][0] = 0 ··· f[N][0] = 0。 有了这些初始值，通过 i 从 1 遍历 N，j 从 1 遍历 V，第 i 种物品的选择数量 k 从 0 遍历到 j / wi 就能一步步求出所有的 f[i][j] 了。
例如求 f[1][1]：
f[1][1] = max{f[0][1]，f[0][0] + 2} = max(0，2) = 2。 求 f[1][2]：
f[1][2] = max{f[0][2]，f[0][1] + 2，f[0][0] + 4} = max(0，2，4) = 4。
最后 f[N][V] 就是要找的答案。
首先朴素地去写
不外乎就是添加了一个条件 对于每个物品我可能放多次 那就枚举一下 该物品不放 到 该物品放最大可放数量 的各种情况
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
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 ++ )
//其实就是在01的基础上 加上一个遍历每个物品放多少次的循环
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]);
//f[i-1][j]包含在后半部分 即k=0的时候
cout << f[n][m] << endl;
}
去除第三层循环的优化
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
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 ++ )
/*
三重循环会tle 试着把这层循环去掉
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]);
把k=1 2 3……代入
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] = Max( f[i-1,j-v] , f[i-1,j-2v]+w , f[i-1,j-3v]+2w...)
可以发现从 f[i,j-v] -> f[i,j] 有很多项相似 也就是说 加入第i个物品 状态变化有规律可言
（本来就是要依靠子问题去更新当前问题的答案 所以提取出上一层与当前层的关系 状态转移方程就好写了）
规律就是 f[i,j]其实就是除第一项外 其他项为f[i,j-v]+w (每一项比原本多了一个w罢了)
那么状态转移方程就可以写成：f[i,j] =Max(f[i-1,j],f[i,j-v]+w)
这样一来就又变成了01背包问题类似的代码
所以得加上个判断 可放入的情况和不可放入的情况
*/
{
//不可放入的情况 直接用上一级答案
f[i][j] = f[i-1][j];
//可放入的情况
if(j>=v[i])
//将找到的规律变形 第一项没规律，保留 其他项有规律 为上一级+w
f[i][j] =max(f[i-1][j], f[i][j - v[i]] + w[i]);
//f[i][j] =max(f[i][j], f[i][j - v[i]] + w[i]);(前面有f[i][j] = f[i-1][j];)
}
cout << f[n][m] << endl;
}
那么可以发现 现在的核心代码和01背包问题的非常相似了
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题
唯一的区别在于 01背包是从上一层i-1的状态得来 而完全背包是从这一层的i的状态得来
那么同样也可以用滚动数组优化
这次要的是滚动后覆盖后的值 所以可以从小到大枚举
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N];
int n, m;
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 ++ )//要的是第i层的覆盖后的j-v[i] 所以从小到大枚举
f[j] = max(f[j], f[j-v[i]] + w[i]);
cout << f[m] << endl;
}
所以到最后 发现和01背包问题只有一个地方不一样——体积是从小到大遍历还是从大到小遍历
而究其原因 就在于 要的是第i-1层的未被覆盖的数据 还是第i层的覆盖后的数据
从大到小是未覆盖的值 从小到大是覆盖后的值
代码实现
朴素实现 O(n*m^2) TLE
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
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[n][m] << endl;
}
去除第三层循环的优化
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
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 ++ ){
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]);
}
}
cout << f[n][m] << endl;
}
滚动数组优化
#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N];
int n, m;
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 ++ )//要的是第i层的覆盖后的j-v[i] 所以从小到大枚举
f[j] = max(f[j], f[j-v[i]] + w[i]);
cout << f[m] << endl;
}
💬 评论