题目描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
题目模型
- 集合表示：f(i，j)
- 集合含义：所有从前i组物品中选，且总体积不大于j的所有选法
- 集合属性：max
- 集合划分：枚举第i组物品选哪个（完全背包枚举第i组背包选几个）
题目代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) { cin>> s[i];
for (int j = 0; j < s[i]; j ++ )
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i ++ ) for (int j="m;">= 0; j -- )
for (int k = 0; 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; } < code></=></=></=></algorithm></iostream>
Original: https://www.cnblogs.com/esico/p/16368077.html
Author: esico
Title: Acwing 9.分组背包问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619913/
转载文章受原作者版权保护。转载请注明原作者出处！