洛谷 P1757：通天之分组背包

【题目来源】https://www.luogu.com.cn/problem/P1757【题目描述】自 01 背包问世之后小 A 对此深感兴趣。一天小 A 去远游却发现他的背包不同于 01 背包他的物品大致可分为 k 组每组中的物品相互冲突现在他想知道最大的利用价值是多少。【输入格式】两个数 m,n表示一共有 n 件物品背包能承受的最大重量为 m。接下来 n 行每行 3 个数 ai​,bi​,ci​表示物品的重量利用价值所属组数。【输出格式】一个数最大的利用价值。【输入样例】45 310 10 110 5 150 400 2【输出样例】10【数据范围】0≤m≤10001≤n≤10001≤k≤100aibici 在 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]), jvol[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 M1e25; const int N1e35; 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() { cinVn; for(int i1; in; i) { cinabc; cnt[c]; vol[c][cnt[c]]a; val[c][cnt[c]]b; mxmax(mx,c); } for(int i1; imx; i) { for(int jV; j0; j--) { for(int k1; kcnt[i]; k) { if(jvol[i][k]) { f[j]max(f[j],f[j-vol[i][k]]val[i][k]); } } } } coutf[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/126202821https://www.cnblogs.com/zbtrs/p/7485110.htmlhttps://blog.csdn.net/m0_75175825/article/details/146893476