背包之分组背包

       分组背包是01背包的进阶问题，但是相对于较为简单，主要难在他的衍生问题。

       分组背包就是现有n个物品，将这些物品分成若干组，给你一个容量为v的背包，对于每一个组中的物品，你最多只能选择一个，问哪些物品装入背包可以使得在体积总和不超过容量v的情况下，价值总和最大。

       可以看出分组背包和01背包有一点细微的差别，01背包是每一种物品最多拿一个，分组背包则变成了每一组最多能拿一个物品。现在我们定义dp[i][j]为前i组物品恰好放入容量为j的背包中的最优选择，dp[i][j]可以由前i - 1组的最优解加上这一组不取物品得到，也可以通过前i - 1个组容量为j - vol[i][k]的最优解再放入当前组的第k个物品得到，依次枚举k的大小，把这一组的所有物品全部遍历完毕，即可得到最终的dp[i][j]，所以可以得到递推公式：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vol[i][k]] + val[i][k])

       其中vol[i][k]表示第i个组别中第k个元素的体积，val[i][k]表示第i个组别中第k个元素的价值。要得到当前的最优解，需要求出前i - 1个组能达到的最优解，然后再在前i - 1个组的基础上加入这一组的元素，对数组元素进行更新。