题目背景 直达通天路·小 A 历险记第二篇
题目描述 自 01 背包问世之后,小 A 对此深感兴趣,一天,小 A 去远游,却发现他的背包不同于 01 背包,
他的物品大致可分为 k 组,每组中的物品相互冲突,现在,他想知道最大的利用价值是多少。
输入格式 两个数 m, n,表示一共有 n 件物品,总重量为 m。 接下来 n 行,每行 3 个数 ai, bi, ci,表示物品的重量,利用价值,所属组数。
输出格式 一个数,最大的利用价值。
输入样例 45 3 10 10 1 10 5 1 50 400 2
输出样例 10
数据范围 1 ≤ m, n ≤ 1000
题解 分组背包(空间优化):
#include <iostream> using namespace std; const int N = 1010; int n, m, a, b, c, MAX; int v[N][N], w[N][N], s[N], f[N]; int main() { cin >> m >> n; for (int i = 1; i <= n; i ++) { cin >> a >> b >> c; s[c] ++; v[c][s[c]] = a; w[c][s[c]] = b; MAX = max(MAX, c); } for (int i = 1; i <= MAX; i ++) for (int j = m; j >= 0; j --) for (int k = 1; k <= s[i]; k ++) if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); cout << f[m] << endl; return 0; }