[
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
// 思路:分组背包等同于01背包中的每个物品有多种选择,在01背包的基础上多加一层循环遍历物品选择即可
#include <iostream>
using namespace std;
const int N = 110;
int n, m, f[N];
int v[N][N], w[N][N], s[N]; // v[i][j]表示第i组的第j个物品体积,s数组保存每一组的物品数量
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &s[i]);
for (int j = 1; j <= s[i]; j ++ )
{
scanf("%d%d", &v[i][j], &w[i][j]);
}
}
for (int i = 1; i <= n; i ++ ) // 遍历每一组
for (int j = m; j > 0; j -- ) // v[i]不存在,所以使用j>0
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]);
printf("%d\n", f[m]);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla