秒懂背包问题之完全背包

题目：已知一个背包最多能容纳物体的体积为V，现有n个物品第i个物品的体积为wi， 第i个物品的重量为ci。且每种物品可以有无限个（0-1背包，一种物品只有一个）。求当前背包最多能装多大重量的物品。

我们根据0-1背包问题进行改造，因为0-1背包每次只考虑拿一次的最大值，而这里我们可以取 [当前背包重量/当前选中的物品体积] 次。然后求最大值。伪代码如下：

 public int knapsack (int V, int n, int[][] vw) {
    // write code here
    int[] dp = new int[V+1];
    for(int i = 1; i<=n;i++){
        for(int j = V;j>=1;j--){
           for(int j =0;j<=V/vm[i-1][0];j--){
                dp[j] = Math.max(dp[j],dp[j-k*vw[i-1][0]]+k*vw[i-1][1]);
            }
        }
    }
    return dp[V];
}

以上是我们根据0-1背包进行改造而成的。下面我们再进行详细比较进行优化。手写dp如下图：

0-1背包问题和完全背包问题的递推关系式区别：
0-1背包的状态由上一条得来，用的是旧数据，所以需要逆向递推；
完全背包的状态由本条前面的数据得来，用的是新数据，所以顺向推即可。（因为我们需要得到前面放了当前物品几次的价值即可，如上图背包容量为5，则当前最大价值为 [当背包容量减去我放当前这个体积]的价值+当前物品体积的价值，即dp[2][5-3]+3, 然后与前一项比较去最大值；再比如容量为6，取dp[2][6-3]+3）。

我们即可以得到递推关系式：
dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1])，我们发现和0-1背包是一致的。
代码如下：

public int knapsack (int V, int n, int[][] vw) {
    // write code here
    int[] dp = new int[V+1];
    for(int i = 1; i<=n;i++){
        for(int j = V;j>=1;j--){
           for(int j =0;j<=V/vm[i-1][0];j--){
                dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
            }
        }
    }
    return dp[V];
}