可能是01背包问题最全面的解析

LeetCode链接

01背包问题：在背包大小能装入的前提下，每个商品最多取一个。

首先，我们有背包大小为4。

• 商品1,商品2，商品3；
• 重量依次为：1,3,4
• 价格依次为：15,20,30；

我们首先采用二维动态数组的方式来解决这个问题。

那么我们首先要确定的是

• 二维动态数组dp[i][j]表示的含义，i表示存入的当前商品i，j表示当前背包的重量。dp[i][j]，在当前背包重量为j的前提下，装入商品i时，能产生的最大价值。
• 我们做一个表格来表示

第一行 0 表示，装入商品0，产生的价值，因为没有商品0，那么我们产生的价值肯定是0，因此第一行为0.

第一列为0，表示如果我的背包大小为0时，所有商品都装不进去，因此产生的价值肯定是0.

那么，我在只能装入商品1时，能产生的价值是多少嗯？如下表所示，只要背包能装下商品1，其产生的最大价值都是15.(因为01背包问题，商品最多装入1次)

那么，我在只能装入商品1和2时，能产生的价值是多少嗯？

• 在背包大小为1或者2时，商品2都放不进去，因此dp[i][j] = dp[i-1][j]
• 在背包大小>=商品2重量时，dp[i][j]，如何更新呢？我们可以看出，
• dp[i][j] = max(dp[i-1][j],当前商品价值+剩余空间还能装入的商品价值)。

那么，我在只能装入商品1，2，3时，能产生的价值是多少嗯？

至此，我们更新dp的准则已经浮现出来了。

• 当背包大小小于当前商品大小时，dp[i][j] = dp[i-1][j]
• 在背包大小>=商品2重量时，dp[i][j] = max(dp[i-1][j],当前商品价值+剩余空间还能装入的商品价值)。

【扩展】如何采用一维数组嗯？代码中包含的有，请自己分析一下

package db;
 
import java.util.Arrays;
 
public class Package01 {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        bag01Program2(weight, value, bagsize);
    }
 
    public static void bag01Program(int[] weight, int[] value, int size) {
        int lengthW = weight.length;
        int[][] dp = new int[lengthW + 1][size + 1];
 
        // 遍历顺序，先遍历物品，在遍历背包容量。
        for (int i = 1; i <= lengthW; i++) {
            for (int j = 1; j <= size; j++) {
                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 上一次最大值，与本次要加入的值和剩余能装的最大值做对比。
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
            }
        }
        for (int[] ints : dp) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(ints[j] + "\t");
            }
            System.out.println();
        }
    }
 
    public static void bag01Program2(int[] weight, int[] value, int size) {
        int lengthW = weight.length;
        int[] dp = new int[size + 1];
 
        // 遍历顺序，先遍历物品，在遍历背包容量。
 
        for (int i = 0; i < lengthW; i++) {
            for (int j = size; j >=weight[i] ; j--) {
                dp[j] = Math.max(dp[j],value[i] + dp[j - weight[i]]);
            }
            System.out.print(Arrays.toString(dp) + "\t");
            System.out.println();
        }
    }
}

这里请思考一下？为什么dp采用一维后，内层循环要倒着写呢？ 

因为要满足：dp[j - weight[i]] 中j - weight[i] >= 0

 for (int i = 0; i < lengthW; i++) {
            for (int j = size; j >=weight[i] ; j--) {
                dp[j] = Math.max(dp[j],value[i] + dp[j - weight[i]]);
            }

【上面】LeetCode答案--采用一维数组。

package db;
 
import java.util.Arrays;
 
public class CanPartition {
    public static void main(String[] args) {
        int[] nums = {1,2,5};
        boolean b = canPartition(nums);
        System.out.println("b = " + b);
    }
    public static boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        if (n == 2) {
            return nums[0] == nums[1];
        }
 
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
 
        // 相当于背包的总重量
        int target = sum / 2;
        // 1、创建动态数组。
        // 容量为j的背包，所背的物品价值可以最大为dp[j]。
        int[] dp = new int[target + 1];
        for (int i = 1; i < target; i++) {
            dp[i] = nums[0];
        }
        // 2、遍历方式
        for(int i = 1; i < n; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
            System.out.print(Arrays.toString(dp) + "\t");
            System.out.println();
        }
        return dp[target] == target;
    }
 
 
}

【总结】

针对背包及其变形问题，

• 第一步先确定背包的大小
• 然后进行动态规划的三步走
  • 确定动态数组
  • 如何遍历
  • 动态数组的更新