通天之分组背包(洛谷)

    科技2025-09-28  55

    题目背景 直达通天路·小 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; }
    Processed: 0.013, SQL: 8