分组背包 完全背包优化

分组背包问题是一种经典的动态规划问题，它是包问题的一个扩展。在分组背包问题中，物品被分为若干组，每组物品只能选择一个进行放入背包。而完全背包问题是背包问题的另一种变体，每种物品都有无限多个可用。

要解决分组背包问题，并进行完全背包优化，可以按照以下步骤进行：

1. 创建一个二维数组 dp，其中 dp[i][j] 表示在前 i 组物品中，背包容量为 j时所能获得的最大价值。

2. 遍历每一组物品 i，从1 到 n：

- 遍历背包容量 j，从0 到背包总容量：

- 对于每个物品 j 属于第 i 组物品的背包问题，进行完全背包优化（即可以选择多个该物品）：

- 对于每个物品 k 属于第 i 组物品，从1 到无穷大：

- 如果 k * weight[i] <= j，则可以选择第 i 组物品的 k个，更新 dp[i][j] 的值：
dp[i][j] = max(dp[i][j], dp[i-1][j-k*weight[i]] + k*value[i])

3. 最终所求解的最大价值为 dp[n][V]，其中 n为组数，V为背包总容量。

这样，我们就可以通过动态规划的方式解决分组背包问题，并进行完全背包优化。