秒懂背包问题之0-1背包

1.分析：

dp[i][j]表示：对于前i个物品，当前背包的容量为j时，这种情况下可以装下的最大价值是dp[i][j]。
如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][j]应该等于dp[i-1][j]。你不装嘛，那就继承之前的结果。
如果你把这第i个物品装入了背包，那么dp[i][j]应该等于dp[i-1] [ j-vm[j-vm[i-1][0] ] + vm[i-1][1]。但还是需要和不装入进行大小比较，取价值最大的。

关键代码如下：

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

2.手写dp表

3.考虑空间的优化

如上面分析所示，我们每次更新第 i 行的数据时，只与 i-1 行有关系，所以我们完全可以使用一维数组来存储dp状态。但我们需要倒着进行更新（因为我们需要用到下标较小的状态）。

核心循环代码如下：

    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--){
                if(j>vw[i-1][0]){
                    dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
                }
            }
        }
        return dp[V];
    }