01背包与完全背包问题

1.递归解法

public static int knapsack(int capacity, int[] weights, int[] values) {
        int n = weights.length;
        //递归的套路，加一个index索引，控制递归到了哪一层
        return bestValue(capacity,n-1,weights,values);
    }

    private static int bestValue(int capacity, int index, int[] weights, int[] values){
        //递归的第一步：终止条件，没有商品了或者背包没容量了就终止
        if(index <= 0 || capacity<= 0){
            return 0;
        }
        //不放的情况
        int res = bestValue(capacity,index-1,weights,values);
        //放的情况，需要剩余满足容量>=weights[index]
        if(capacity >= weights[index]){
            //放的情况为bestValue(capacity - weights[index],index-1,weights,values)。也就是index放进去。其他的容量放
            //前面index-1
            res = Math.max(res,values[index]+bestValue(capacity - weights[index],index-1,weights,values));
        }
        return res;
    }

递归解法存在大量的重复计算。导致效率不高。下面可以进一步优化。

--------------------------------------------------------------------------------------------

2.记忆搜索解法。

申请一个二维数组用来记录重叠子问题。用空间换时间。

public static int knapsack(int capacity, int[] weights, int[] values) {
        int n = weights.length;
        //因为有商品和价值两个维度，所以需要用一个二维的空间来记录
        memo = new int[n][capacity+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= capacity ; j++) {
                memo[i][j] = -1;

            }
        }
        return bestValue(capacity,n-1,weights,values);
    }

    private static int bestValue(int capacity, int index, int[] weights, int[] values){
        //递归的第一步：终止条件，没有商品了或者背包没容量了就终止
        if(index <= 0 || capacity<= 0){
            return 0;
        }
        //如果已经有缓存，直接从缓存中取即可，避免重复计算
        if (memo[index][capacity] != -1){
            return memo[index][capacity];
        }
        //不放的情况
        int res = bestValue(capacity,index-1,weights,values);
        //放的情况，需要剩余满足容量>=weights[index]
        if(capacity >= weights[index]){
            //放的情况为bestValue(capacity - weights[index],index-1,weights,values)。也就是index放进去。其他的容量放
            //前面index-1
            res = Math.max(res,values[index]+bestValue(capacity - weights[index],index-1,weights,values));
        }
        //将计算的结果加入缓存
        memo[index][capacity] = res;
        return res;
    }

记忆搜索虽然在时间复杂度上已经满足要求，但是递归需要大量堆栈上的空间，容易造成栈溢出。最好能将递归转换成递推。

==========================================================================

3.动态规划解法。动态规划其实就是一个填表的过程。下面举个例子说明整个过程。

假设有一个容量为5的背包以及3个物品

申请一个二维表格dp，并将第一行和第一列初始化。初始化的规则为。

对于第一行，第一行表示只有一个物品。所以只要capacity >= weights[0]，就初始化为values[0]。

对于地理列，第一列表示背包容量为0的时候，所以第一列的值都为0

然后填dp[1][1]

public static int knapsack(int capacity, int[] weights, int[] values) {
        assert (weights.length == weights.length);
        int len = weights.length;
        if(len == 0){
            return 0;
        }
        //dp表示i个物品放进容量为c的背包的效益
        int[][] dp = new int[len][capacity+1];
        //初始化第一列，第一列表示背包容量为0的时候，所以第一列的值都为0
        for (int i = 0; i < len ; i++) {
            dp[i][0] = 0;
        }
        //初始化第一行。第一行表示只有一个物品。所以只要capacity >= weights[0]，就初始化为values[0]
        for (int i = 1; i <= capacity ; i++) {
            dp[0][i] = capacity >= weights[0]?values[0]:0;
        }
        for (int i = 1; i < len ; i++) {
            for (int j = 1; j <= capacity ; j++) {
                //第i个物品放不时的结果，和只有i-1个物品的结果一样
                dp[i][j] = dp[i-1][j];
                //第i个物品能放下
                if(j >= weights[i]){
                    //比较放和不放哪种能产生更高的价值
                    dp[i][j] = Math.max(dp[i][j],values[i]+dp[i-1][j-weights[i]]);
                }
            }
        }
        return dp[len-1][capacity];

    }

=======================================================================

4.空间压缩。从填表的过程可以看出。其实每次只依赖上一行。因此用一个2行的数组即可表示整个过程。

public static int knapsackDp(int capacity, int[] weights, int[] values) {
    assert (weights.length == weights.length);
    int len = weights.length;
    if(len == 0){
        return 0;
    }
    //dp表示i个物品放进容量为c的背包的效益
    int[][] dp = new int[2][capacity+1];
    for (int i = 0; i < 2 ; i++) {
        dp[i][0] = 0;
    }
    for (int i = 1; i <= capacity ; i++) {
        dp[0][i] = capacity >= weights[0]?values[0]:0;
    }
    for (int i = 1; i < len ; i++) {
        for (int j = 1; j <= capacity ; j++) {
            dp[i%2][j] = dp[(i-1)%2][j];
            //第i个物品能放下
            if(j >= weights[i]){
                dp[i%2][j] = Math.max(dp[(i-1)%2][j],values[i]+dp[(i-1)%2][j-weights[i]]);

            }
        }
    }
    return dp[(len-1)%2][capacity];
}

=================================================================

5.空间继续压缩。用一行也可以。

public static int knapsack(int capacity, int[] weights, int[] values) {
        assert (weights.length == weights.length);
        int len = weights.length;
        if(len == 0){
            return 0;
        }
        //dp表示i个物品放进容量为capacity的背包的效益
        int[] dp = new int[capacity+1];
        //只放第0个物品，只有能放下。产生的价值就是values[0]，否则为0
        for (int i = 0; i <= capacity ; i++) {
            dp[i] = i >= weights[0]?values[0]:0;
        }
        for (int i = 1; i < len ; i++) {
            //注意一定为倒序，j < weights[i]的话，表示放不下了。那么可以终止循环。这是动态规划中
            //一个常用的做法。减枝
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j],values[i]+dp[j-weights[i]]);

            }
        }
        return dp[capacity];

    }

为什么要强调递推过程是逆序的呢？

举个例子

假设n=1，背包容量c=5，只有一个物品，w和v都为1，倒着推得结果为
      0     1     2     3     4     5
1     0     1     1     1     1     1

正着推得结果为
      0     1     2     3     4     5
1     0     1     2     3     4     5

其实正向递推为完全背包。

因为倒着推。每个物品只有一次选择的机会，放或者不放。

正向推。每个物品在每次都可以选择放或者不放。所以是完全背包。
完全背包代码如下

public static int knapsack(int capacity, int[] weights, int[] values) {
        assert (weights.length == weights.length);
        int len = weights.length;
        if (len == 0) {
            return 0;
        }
        //dp表示i个物品放进容量为capacity的背包的效益
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < len; i++) {
            //必须满足容量>=weights[i]才能放入
            for (int j = weights[i]; j <= capacity; j++) {
                dp[j] = Math.max(dp[j], values[i] + dp[j - weights[i]]);
            }
        }
        return dp[capacity];

    }

一些背包问题相关的算法题解析请参考此博文