洛谷 P1757：通天之分组背包

​【题目来源】
https://www.luogu.com.cn/problem/P1757

【题目描述】
自 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

【数据范围】
0≤m≤1000，1≤n≤1000，1≤k≤100，
ai，bi，ci 在 int 范围内。

【算法分析】
因为每组最多选择一个物品，所以可以将每组都看作一个整体，这就类似于 0/1 背包问题。
● 令 f[i][j] 表示将前 i 组物品放入容量为 j 的背包中可以获得的最大价值，vol[i][k] 表示第 i 组第 k 个物品的体积，val[i][k] 表示第 i 组第 k 个物品的价值，cnt[i] 表示第 i 组物品的个数，则分组背包问题的状态转移方程为：f[i][j]=max(f[i-1][j], f[i-1][j-vol[i][k]]+val[i][k]), j>=vol[i][k]
● 与 0/1 背包问题一样，可以对分组背包问题二维实现的状态转移方程进行一维数组优化，可得：
f[j]=max(f[j], f[j-vol[i][k]]+val[i][k])
其中，f[j] 表示将物品放入容量为 j 的背包中可以获得的最大价值。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int M=1e2+5;
const int N=1e3+5;
int vol[M][N],val[M][N],cnt[M];
int f[N];
int mx; //Maximum group number
int V,n,a,b,c;

int main() {
    cin>>V>>n;
    for(int i=1; i<=n; i++) {
        cin>>a>>b>>c;
        cnt[c]++;
        vol[c][cnt[c]]=a;
        val[c][cnt[c]]=b;
        mx=max(mx,c);
    }

    for(int i=1; i<=mx; i++) {
        for(int j=V; j>=0; j--) {
            for(int k=1; k<=cnt[i]; k++) {
                if(j>=vol[i][k]) {
                    f[j]=max(f[j],f[j-vol[i][k]]+val[i][k]);
                }
            }
        }
    }
    cout<<f[V]<<endl;

    return 0;
}

/*
in:
45 3
10 10 1
10 5 1
50 400 2

out:
10
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/126202821
https://chuna2.787528.xyz/zbtrs/p/7485110.html
https://blog.csdn.net/m0_75175825/article/details/146893476

 

​