题目

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

0 - 1 背包问题背后的图

0-1背包.png

解法思路（一）记忆化递归

问题状态的定义

• F(n, C) 考虑将 n 个物品，放进容量为 C 的背包，是价值最大；

价值最大的两种情况

• 第 n - 1 个元素不放进背包中，背包中的价值最大，对应的状态为：F(n-2, C)；
• 第 n - 1 个元素放进背包中，背包中的价值最大，对应的状态为：v[n-1] + F(n-2, C-w[n-1]；

哪种情况的价值最大？

• max( F(n-2, C), v[n-1] + F(n-2, C-w[n-1]) )

解法实现（一）记忆化递归

实现细节

• 记忆数组 memo 是二维的；

package knapsack;

public class Solution1 {

    private int[][] memo;

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        memo = new int[n][C + 1];
        return bestValue(w, v, n - 1, C);
    }

    // 用 [0...index] 的物品,填充容积为c 的背包的最大价值
    private int bestValue(int[] w, int[] v, int index, int c){

        if(c <= 0 || index < 0)
            return 0;

        if(memo[index][c] != -1)
            return memo[index][c];

        int res = bestValue(w, v, index-1, c);
        if(c >= w[index])
            res = Math.max(res,
                    v[index] + bestValue(w, v, index - 1, c - w[index]));

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

}

解法思路（二）动态规划

思路描述

• 把头 1 个元素放进背包中，最大价值就是数组中 memo[0][C]；
• 把头 2 个元素放进背包中，最大价值就是数组中 memo[1][C]；
• ...
• 把头 n 个元素放进背包中，最大价值就是数组中 memo[n - 1][C]；

memo 数组怎么填？

• 从左上角到右下角一行一行一格一格的填；
• 第一行的填法是：容量比 w[0] 小的的格都填 0，其余都填 v[0]；
• 第二行开始的填法：
  • 容量比 w[i] 小的格，把头顶上那格 memo[i-1][j] 的值落下来；
  • 容量大于等于 w[i] 的格，比较 memo[i-1][j] 和 v[i] + memo[i - 1][j - w[i]] 的值的大小；

解法实现（二）动态规划

实现细节

• 从数组 memo 的左上开始填，一直填到右下，右下角的值就是背包问题的题解；

package knapsack;

public class Solution2 {

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        int[][] memo = new int[n][C + 1];

        for(int j = 0 ; j <= C ; j ++)
            memo[0][j] = (j >= w[0] ? v[0] : 0 );

        for(int i = 1 ; i < n ; i ++)
            for(int j = 0 ; j <= C ; 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[n - 1][C];
    }

}

解法实现（三）动态规划 优化

优化结果

• 空间复杂度从 n * C 变成 2 * C；

package knapsack;

public class Solution3 {

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        int[][] memo = new int[2][C + 1];

        for(int j = 0 ; j <= C ; j ++)
            memo[0][j] = (j >= w[0] ? v[0] : 0);

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

        return memo[(n-1) % 2][C];
    }

}

解法实现（四）动态规划 优化

优化结果

• 空间复杂度从 2 * C 变成 C；

package knapsack;

public class Solution4 {

    public int knapsack01(int[] w, int[] v, int C){

        if(w == null || v == null || w.length != v.length)
            throw new IllegalArgumentException("Invalid w or v");

        if(C < 0)
            throw new IllegalArgumentException("C must be greater or equal to zero.");

        int n = w.length;
        if(n == 0 || C == 0)
            return 0;

        int[] memo = new int[C+1];

        for(int j = 0 ; j <= C ; j ++)
            memo[j] = (j >= w[0] ? v[0] : 0);

        for(int i = 1 ; i < n ; i ++)
            for(int j = C ; j >= w[i] ; j --)
                memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]);

        return memo[C];
    }

}

算法 [Java] 目录