0-1 背包问题

0 - 1 背包问题是 一种经典的动态规划问题。

什么是 0-1 背包问题？

假设有n个物品，其价值为 v[ ], 重量为 w[ ]， 选取一部分物品放入容量为 C 的背包，问如何选取物品，使得背包内物品的总价值最多。

自顶向下 解决

如 v=[6, 10, 12], w=[1, 1, 3], C=5。

可以看出整个过程是一个递归过程。其中每一个节点的 idx,c 表示考虑将 v[idx,...] 物品尝试放入 容量为c的背包。如果idx>=v.length 或者 c<=0 说明无法继续放入，return 0。否则需要比较向左右两条支路向底部递归的结果，选取最大值。对于 memo[idx][c]每次都要考虑两种策略，一种是将 v[idx] 放入背包（如果剩下的容积允许），减去 w[i] 容积后继续向下递归 。另一种是不将v[idx] 放入背包，继续向下递归。为了避免重复计算，很自然的想到用一个 二维数组 memo[v.length][C]存储已经计算过的结果。

// 01背包问题
public class Knapsack01 {

    int[][] memo;

    //  自顶向下 + 剪枝
    public int solution1(int[] v, int[] w, int C)
    {
        memo=new int[v.length][C+1];//memo[idx][c]

        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < C+1; j++) {
                memo[i][j]=-1;
            }
        }
        return dfs(v,w,0,C);
    }

    //将 价值为v[idx,...], 体积为 w[idx,...] 的物品放入容积为 c 的背包
    private int dfs(int[] v, int[] w, int idx, int c ){

        if (idx>=v.length || c<=0  ){
            return 0;
        }

        if (memo[idx][c]!=-1){
            return memo[idx][c];
        }

        int res=0;
        if (c>=w[idx]){
            res=Math.max(res,v[idx]+dfs(v,w,idx+1,c-w[idx]));
            res=Math.max(res,dfs(v,w,idx+1,c));
        }
        else{
            res=Math.max(res,dfs(v,w,idx+1,c));
        }

        memo[idx][c]=res;
        return memo[idx][c];
    }     

}

自底向上 解决

如 v=[6, 10, 12], w=[1, 1, 3], C=5。

我们可以列出下面这张表格，假设这张表格叫 memo, 那么 memo[idx][c] 表示 从 v[0,... idx] 中放入容积为c的背包的最大价值。

对于 memo[idx][c] 也有两种策略, 一种是 v[idx] 不放入背包, 那么memo[idx][c] = memo[idx-1][c]。另一种是 将 v[idx] 放入背包(如果容积允许的话),并且继续计算memo[idx-1][c-w[idx]]。

如果用状态转移公式表示的话，就是 F(i,c) = max( F(i-1,c) , v [ i ] + F(i-1, c-w [i]) )。

为此我们需要一开始将表格的第一行初始化, 以便计算后面的行。

// 01背包问题
public class Knapsack01 {

    int[][] memo;

    // 自底向上
    public int solution2(int[] v, int[] w, int C)
    {
        memo=new int[v.length][C+1];//memo[idx][c]

        for (int  j= 0; j < C+1; j++) {
            if (w[0]<=j){
                memo[0][j]=v[0];
            }else {
                memo[0][j]=0;
            }
        }

        for (int i = 1; i < v.length; i++) {
            for (int j = 0; j < C+1; j++) {
                memo[i][j]=memo[i-1][j];
                if (j>=w[i]){
                    memo[i][j]=Math.max(memo[i][j],v[i]+memo[i-1][j-w[i]]);
                }
            }
        }
        
        return memo[v.length-1][C];
    }
     
}