1268:【例9.12】完全背包问题

完全背包问题是一个经典的动态规划问题，在给定背包容量和一组物品的重量和价值的情况下，如何选择物品放入背包中，使得总价值最大化。

举个例子来说明，假设背包容量为C，有n个物品，每个物品的重量分别为w1, w2, ..., wn，对应的价值为v1, v2, ..., vn。我们需要选择哪些物品放入背包中，使得总价值最大。

可以使用动态规划的方法来解决这个问题。定义一个二维数组dp[i][j]，其中dp[i][j]表示前i个物品放入容量为j的背包中所能达到的最大价值。

状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i][j-wi] + vi)

其中，dp[i-1][j]表示不选择第i个物品，dp[i][j-wi] + vi表示选择第i个物品放入背包中。

最终的结果就是dp[n][C]，即前n个物品放入容量为C的背包中所能达到的最大价值。

这个问题可以通过动态规划的思想进行求解，时间复杂度为O(nC)。同时可以通过空间优化，将二维数组优化为一维数组，降低空间复杂度为O(C)。