分组背包，通俗的讲就是，给你N组物品，然后每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大.

其实就类似于01背包，对于一个物品有两种决策选或不选，但是分组背包是在01背包的基础上对物品进行了分组，并且每一组只能最多选择一个物品，所以我们不妨用01背包的思想去思考分组背包.

分析：我们设f[i][j]为当前考虑到了第i组物品，剩余容里为j的背包能装物品的最大价值，那么很容易想到我们需要去枚举第i组物品，考虑选哪一个物品时最优的(或者不选)，状态转移方程就是 i f ( j > = v [ i ] [ k ] ) f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] ) if(j>=v[i][k]) f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]) if(j>=v[i][k])f[i][j]=max(f[i][j],f[i−1][j−v[i][k]]+w[i][k]),v[i][k]和w[i][k]分别表示第i组物品中第k个物品的体积和价值

代码：