分组背包问题是背包问题的一种变体，它在一组物品中进行选择，每个物品属于某个特定的组。问题的描述通常是这样的：给定若干组物品，每组物品都有自己的重量、价值以及数量限制。目标是选择若干组物品放入背包中，使得背包中物品的总价值最大。
这里用acwing上的例题：9. 分组背包问题 - AcWing题库
朴素解法
这里朴素解法利用的二维数组f[i][j]来进行状态转移，枚举物品组数，枚举体积，枚举对于每组物品的决策，选还是不选，以得到最优解。这里朴素解法不再详细介绍，只放一个代码段，因为后面还可以优化一下。
其实看起来跟多重背包的朴素解法差不多，有什么不同的，下面放上了两段代码，比较看一下。不同在了就是在状态转移上了，多重背包呢可以选多个所以用k来控制，分组背包呢，例题中一组背包中最多只允许选一个，就是对于一组背包可以不选可以选一个。每一个物品都是不同的、有个性的，没有完全相同的，第三个for循环就是在枚举每一组具体的物品。
一维优化解法
对照朴素解法，多重背包呢时间复杂度那个for循环k的可以优化掉，空间复杂度也可以优化成一维的，但是时间复杂度优化是有条件的，多重背包呢可以组合进行二进制优化，也可以分类进行单调队列优化。分组背包呢，第i组物品的体积价值都是各不相同的，毫无规律可言，何以优化，但是在空间复杂度上可以优化成一维，f[i][j]是在f[i-1][j]转移过来的，就是在前一组物品决策完转移过来的，只是用了上一行的数据，有点类似01背包的一维优化。
#include<iostream> using namespace std; int dp[1005],v[1005],w[1005];//dp[i]表示背包容量为i时所获得最大价值 int N,V; int main(){ cin>>N>>V; int p;//p表示第p组物品 for(int i=1;i<=N;i++){ cin>>p; for(int j=1;j<=p;j++){ cin>>v[j]>>w[j]; } //因为dp[j]会先于dp[j-v[k]]更新，所以dp[j-v[k]]的值等价于dp[i-1][j-v[k]] for(int j=V;j>=1;j--){//逆序枚举背包容量 for(int k=1;k<=p;k++){ if(j>=v[k]){ dp[j]=max(dp[j],dp[j-v[k]]+w[k]); } } } } cout<<dp[V]<<endl; return 0; }
这里注意枚举背包容量和枚举k顺序不可颠倒，不然dp[j-v[k]]的值就不等价于dp[i-1][j-v[k]]了。
变式题型
小编做过其他类型的题，但都是分组背包的变式。有的题呢，一组物品给你限定了选多少个，比如选2个3个，例题中最多选一个，这样的话就比较麻烦了，既要确定选了哪一组物品又要达到选几个的要求，还是再次基础上，利用贪心，在每一组背包选几个的要求基础上，使得每一组背包都是最优的就可以（01背包）。用背包容量去枚举每一组背包，再去加一个if判断是否达到选几个的要求。有的呢还会物品会乱序输入，让你自己去分组好，再去进行选择。下面放一个我写过的题的代码，组数打乱自己找的（当然题中样例每打乱）。
#include<iostream> #include<vector> using namespace std; int w[31],c[31]; int dp[201]; int v,n,p,t; int main(){ cin>>v>>n>>t;//v容量n物品t组数 vector<vector<int>> group(t+1); for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]>>p;//p属于第几组 group[p].push_back(i);//把下标往里抛就行 } for(int i=1;i<=t;i++){//与一维优化类似 for(int j=v;j>=0;j--){ for(int k=0;k<group[i].size();k++){ int index=group[i][k]; if(j>=w[index]){ dp[j]=max(dp[j],dp[j-w[index]]+c[index]); } } } } cout<<dp[v]<<endl; return 0; } /* 10 6 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3 */ //20
分组背包呢，听起来就是分组分组……，无非还是01背包的变形，背包问题呢，变形非常多，但是万变不离其宗，方法会了，其他变式也都迎刃而解。小编水平有限，能说的都在文章展现了，有错误的地方请大家指出，大家有疑问的地方随时可以私信我，看到必答。下篇更新有依赖的背包。
