0-1背包问题讲解 ＆ leetcode相关题目总结

1 0-1背包问题理论基础

1.1 0-1背包问题描述

0-1背包问题描述

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

其实这个问题我们也可以用暴力解法，每一件物品其实只有两个状态，取或者不取，所以可以使用 回溯法 搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。暴力的解法是 指数级别 的时间复杂度。进而才需要动态规划的解法来进行优化！

在下面的讲解中，我举一个例子：背包最大重量为4。物品为：

问背包能背的物品最大价值是多少？

1.2 二维dp数组实现

1.2.1 理论讲解

1. 确定dp数组以及下标的含义

• dp[i][j] 表示从下标为 0 ~ i 的物品里任意取，放进 容量为j 的背包，价值总和最大是多少。

2. 确定递推公式

每个物品只有 放 和 不放 两种状态，所以可以有两个方向推出来dp[i][j]。

• 不放物品i：此时dp[i][j] 由 dp[i - 1][j] 推出，即背包容量为j，里面不放物品i的最大价值，此时 dp[i][j] = dp[i - 1][j]。
• 放物品i：此时dp[i][j] 由 dp[i - 1][j - weight[i]] 推出，dp[i - 1][j - weight[i]] 为 背包容量为j - weight[i] 的时候 不放物品i 的 最大价值，那么 dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是 背包放物品i得到的最大价值。

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化

• 首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。即 dp[i][0] = 0。
• 其次，由状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出 i 是由 i - 1 推导出来，那么 i 为 0 的时候就一定要初始化。 dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
  • 那么很明显当 j < weight[0] 的时候，dp[0][j] = 0，因为背包容量比编号0的物品重量还小。
  • 当 j >= weight[0] 时，dp[0][j] = value[0]，因为背包容量放足够放编号0物品。

4. 确定遍历顺序

可以看出，有两个遍历的维度：物品与背包重量。先遍历物品后遍历背包更好理解，但是先遍历背包再遍历物品也是可以的。

1.2.2 代码实现

public static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {
    
    int[][] dp = new int[weight.length][bagSize+1];
    // 初始化
    for (int i = 0; i < dp.length; i++) {
     // 可以省略
        dp[i][0] = 0;
    }
    for (int j = 0; j < dp[0].length; j++) {
    
        if (j < weight[0]) {
    
            dp[0][j] = 0;
        } else {
    
            dp[0][j] = value[0];
        }
    }

    for (int i = 1; i < dp.length; i++) {
    
        for (int j = 0; j < dp[0].length; j++) {
    
            if (j < weight[i]) {
    
                dp[i][j] = dp[i-1][j];
            } else {
    
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);
            }
        }

    }

    for (int i = 0; i < dp.length; i++) {
    
        for (int j = 0; j < dp[0].length; j++) {
    
            System.out.print(dp[i][j]+" ");
        }
        System.out.println();
    }
}

1.3 一维数组（滚动数组）实现

滚动数组就是把二维dp降为一维dp。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);。与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

1.3.1 理论讲解

1. 确定dp数组以及下标的含义

• dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2. 确定递推公式

• 当 j >= weight[i] 时，也就是背包容量能放下物品 i 时，此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i。所以递归公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. dp数组如何初始化

• dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

4. 确定遍历顺序

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

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。这是为什么呢？

倒序遍历是为了保证物品i只被放入一次！但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

• dp[1] = dp[1 - weight[0]] + value[0] = 15
• dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

• dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
• dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

1.3.2 代码实现

public static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {
    
    int[] dp = new int[bagSize + 1];

    for (int i = 0; i < weight.length; i++) {
    
        for (int j = dp.length - 1; j >= weight[i]; j--) {
    
            dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[i]);
        }
        for (int j = 0; j < dp.length; j++) {
    
            System.out.print(dp[j]+" ");
        }
        System.out.println();

    }
}

2 leetcode相关题目

416. 分割等和子集

题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路分析

我们要想把 0-1背包问题套到本题上来需要明确如下四点：

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

代码实现

public boolean canPartition(int[] nums) {
    
    int sum = 0;
    for (int num : nums) {
    
        sum += num;
    }
    if (sum % 2 == 1) {
    
        return false;
    }
    int bagSzie = sum / 2;
    int[] dp = new int[bagSzie + 1];

    for (int i = 0; i < nums.length; i++) {
    
        for (int j = dp.length - 1; j >= nums[i] ; j--) {
    
            dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[bagSzie] == bagSzie;
}

1049. 最后一块石头的重量 II

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。思路和 416. 分割等和子集 差不多。

public int lastStoneWeightII(int[] stones) {
    
    int sum = 0;
    for (int stone : stones) {
    
        sum += stone;
    }
    int target = sum / 2;
    int[] dp = new int[target + 1];
    for (int i = 0; i < stones.length; i++) {
    
        for (int j = dp.length - 1; j >= stones[i] ; j--) {
    
            dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - dp[dp.length - 1] * 2;
}

494. 目标和（注意递推公式有所不同）

思路一：动态规划

思路分析

本题其实转换一下思路其实和 416. 分割等和子集 差不多。

本题要如何使表达式结果为target，

既然为target，那么就一定有 left组合 - right组合 = target。

left + right等于sum，而sum是固定的。

公式来了， left - (sum - left) = target ==> left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

1. 确定dp数组以及下标的含义

• dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

2. 确定递推公式

不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。

例如：nums: [1, 2, 3, 4, 5]，dp[j]，j 为 5，先遍历物品后遍历背包：

• 背包中有 nums[0]=1 的话，有 dp[4] 种方法 凑成 dp[5]。
• 背包中有 nums[1]=2 的话，有 dp[3]种方法 凑成 dp[5]。
• 背包中有 nums[2]=3 的话，有 dp[2]中方法 凑成 dp[5]。
• 背包中有 nums[3]=4 的话，有 dp[1]中方法 凑成 dp[5]。
• 背包中有 nums[4]=5 的话，有 dp[0]中方法 凑成 dp[5]。

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：dp[j] += dp[j - nums[i]]

3. dp数组如何初始化

从递归公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递归结果将都是0。

dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。

4. 确定遍历顺序

对于01背包问题一维dp的遍历，第一节中也提到了：nums放在外循环，target在内循环，且内循环倒序。

代码实现

public int findTargetSumWays(int[] nums, int target) {
    
    int sum = 0;
    for (int num : nums) {
    
        sum += num;
    }
    if ((sum + target) % 2 == 1) {
    
        return 0;
    }
    int bagSize = (sum + target) / 2;
    if (bagSize < 0) {
    
        bagSize = -bagSize;
    }
    int[] dp = new int[bagSize+1];
    dp[0] = 1;
    for (int i = 0; i < nums.length; i++) {
    
        for (int j = dp.length - 1; j >= nums[i] ; j--) {
    
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[bagSize];

}

思路二：回溯

class Solution {
    
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
    
        backtrack(nums, target, 0, 0);
        return count;
    }

    public void backtrack(int[] nums, int target, int index, int sum) {
    
        if (index == nums.length) {
    
            if (sum == target) {
    
                count++;
            }
        } else {
    
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}