分组背包问题思路分析
同样对于dp问题采用 闫氏dp分析法
| 集合 : 从1 ~ i 组物品中选,且总体积不超过j的集合
|
|
|----------状态表示--------|
| |
| |
| |属性 : 集合中所有可行方案中价值的最大值 max
DP
|
|
|
|
|----------状态计算 : 根据集合划分,将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
对集合f(i,j) , 这个集合我们可以可以分为若干个集合,由于分组背包问题,每一组中只能选一个,故其子集有
(1选择第一个物品 (2) 选择第2个物品 (3) 选择第三个物品 ..... (k) 选择第k个物品
当然这里别忘了还有不选择 第 i 组的情况的子集 故我们可以写出状态计算 f(i,j) = max { f(i - 1, j - v(i,k)) + w[i,k] }; 这里的k 从 0 ~ k;
故代码如下
#include<iostream>
using namespace std;
constexpr int N = 110;
int n,m;
int v[N][N], w[N][N], s[N];
int f[N][N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> s[i];
for(int j = 1; j <= s[i]; ++j)
{
cin >> v[i][j] >> w[i][j];
}
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
for(int k = 0; k <= s[i]; ++k) // 注意这里的k是从0开始的,就是考虑第i组不选的情况
{
if(v[i][k] <= j)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
我个人的话喜欢,首先将集合分为两部分(1) 不包含第i组的部分 (2) 必须包含第i组的部分
(1) 部分很好表示就是 f(i - 1, j) , (2) 部分为上面分析的是包含第i组的第一个物品,还是第二个物品,还是第k个物品, 这样思考的话代码可以写为:
#include<iostream>
using namespace std;
constexpr int N = 110;
int n,m;
int v[N][N], w[N][N], s[N];
int f[N][N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> s[i];
for(int j = 1; j <= s[i]; ++j)
{
cin >> v[i][j] >> w[i][j];
}
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
f[i][j] = f[i - 1][j]; // 这里为 f(i,j) 的第一部分
for(int k = 1; k <= s[i]; ++k) // 这里for的k从1开始, 为f(i,j)的第二部分
{
if(v[i][k] <= j)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
自我总结
这里在写上面那一种写法的时候,第一次将f[i][j] = f[i - 1][j];写到了 第三层的k的for循环中,导致答案一直是WA。因为写到第三层for之后
每次遍历k的时候,总会把此时的f(i,j)更新为 f(i - 1, j), 也许后面进入不了下面的if,导致其更新为错误的值。
空间优化 —》 一维数组的写法
#include<iostream>
using namespace std;
constexpr int N = 110;
int n,m;
int v[N][N], w[N][N], s[N];
int f[N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> s[i];
for(int j = 1; j <= s[i]; ++j)
{
cin >> v[i][j] >> w[i][j];
}
}
for(int i = 1; i <= n; ++i)
for(int j = m; j >= 1; --j) // 注意这里的j记得倒序
for(int k = 1; k <= s[i]; ++k)
if(v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}