背包问题

导语

最近刷力扣每日一题的时候，又碰到了动态规划的题目，而且它这种题型是典型的背包问题。题目如下（力扣1262）：

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例 1：

1
2
3

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

1
2
3

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：

1
2
3

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

提示：

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

为什么说它是背包问题呢？首先，它和01背包一样，都给定了一个限定条件，只不过01背包是容量限制，而这道题是余数限制。还有，都是从集合中进行选择，对于第i个元素，都有选和不选两种选择，最终的目的都是使得target最优。

本题最合适的方法便是动态规划，下面是分析的过程：

子问题分析

状态转移方程

定义dp[i][j]为nums[0, i]（双闭区间）内余数和为j的最大值，那么状态转移方程如下：

1	dp[i][loc] = Math.max(dp[i][loc], num);

其中：

1 2	int num = dp[i-1][j]+nums[i]; int loc = num % 3;

完整的java代码如下：

class Solution {
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][3];
        dp[0][nums[0]%3] = nums[0];
        for (int i = 1; i < n; i++) {
            System.arraycopy(dp[i-1],0,dp[i],0,3);
            for (int j = 0; j < 3; j++) {
                int num = dp[i-1][j]+nums[i];
                int loc = num % 3;
                dp[i][loc] = Math.max(dp[i][loc], num);
            }
        }
        return dp[n-1][0];
    }
}

由于第i层的结果依赖于第i-1层，因此我们可以将矩阵进行纵向压缩，优化后的Java代码如下：

class Solution {
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        int[] pre = new int[3], dp = new int[3];
        pre[nums[0]%3] = nums[0];
        for (int i = 1; i < n; i++) {
            System.arraycopy(pre,0,dp,0,3);
            for (int j = 0; j < 3; j++) {
                int num = pre[j]+nums[i];
                int loc = num % 3;
                dp[loc] = Math.max(dp[loc], num);
            }
            System.arraycopy(dp,0,pre,0,3);
        }
        return dp[0];
    }
}

和01背包的相似之处

我们知道，01背包的dp矩阵规模为dp[n][c+1]，压缩之后为dp[c+1]，而此题的dp矩阵规模为dp[n][3]，压缩之后为dp[3]。

而c和3，一个是指容量，一个是指余数，两个都是限定条件。

再看递推方程，两个都是根据前面一个子问题的情况求解当前子问题。

其实，这样类似的题还有很多，下面是力扣常见的背包问题：

力扣416 分割等和子集 01背包是否问题
力扣322 零钱兑换完全背包最值问题
力扣518 零钱兑换2 完全背包组合问题
力扣494 目标和 01背包组合问题
力扣139 单词拆分完全背包排列问题
力扣279 完全平方数完全背包组合问题
力扣377 组合总和4 完全背包排列问题

背包问题描述

背包问题可以描述为——从物品集合中选取物品至背包，在拿放过程中可能涉及到的求解任务有：

背包可以容纳物品的最大价值（背包最值）
背包容纳指定价值物品的组合数（背包组合）
背包能否容纳指定价值的物品（背包是否）

背包问题主要分为01背包与完全背包。

01背包是指物品集中每个物品只能拿取一次，完全背包是指物品集中每个物品无限制次数拿取。

第一题：分割等和子集（力扣416）（01背包是否问题）

题目描述见力扣，该题目可以转化为——从给定数组（物品集）中拿取数字，使背包物品价值（求和）恰好等于数组和的一半。所以这是一个01背包是否问题。

首先判断数组和是否为偶数，不是偶数显然无法分割等和子集。接着求数组中的最大值，如果最大值大于数组和的一半，显然也无法分割等和子集。

这些判断条件是必要的。如果不经过判断直接使用dp背包有的case会出错。比如数组和为奇数的数组，其除以2向下取整后得到的目标target是错误的（真正的目标target是浮点数）；比如说如果存在数组中最大值大于数组和一半的情况，那后续dp数组初始化会报错，因为最大值比target大，初始化时一定会数组越界。

接下来就是构建背包dp数组，是本题的重头戏。

1	int[][] dp = new int[n][target+1];

dp[i][j]的意义是：对于输入数组nums，在给定nums[0,i]区间（双闭区间）内，能否找到数字组合使其总和为j。显而易见，数组所有值先设为False。

然后是二维数组的初始化。

一般来说dp数组最重要的是递推公式的构建。这就要求数组的第一行与第一列初始值必须是正确的，这样才能保证依赖这些初始值进行的递推计算是正确的。

该题的初始化操作为

// target为的位置全部初始化为true
// dp[i][nums[i]]的位置也一定为true
for (int i = 0; i < n; i++) {
    dp[i][0] = true;
    dp[i][nums[i]] = true;
}

递推公式如下：

for (int i = 1; i < n; i++) {
    for (int j = 1; j <=target; j++) {
        if (j >= nums[i]) {
            // 两种情况有一种为true的话便成立
            dp[i][j] = dp[i-1][j]|dp[i-1][j-nums[i]];
        } else {
            dp[i][j] = dp[i-1][j];
        }
    }
}

完整的Java代码如下：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int max = Arrays.stream(nums).max().getAsInt();
        if (sum % 2 == 1) return false;
        int target = sum / 2, n = nums.length;
        if (max > target) return false;
        boolean[][] dp = new boolean[n][target+1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
            dp[i][nums[i]] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <=target; j++) {
                if (j >= nums[i]) {
                    // 两种情况有一种为true的话便成立
                    dp[i][j] = dp[i-1][j]|dp[i-1][j-nums[i]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n-1][target];
    }
}

上面的代码用到了一个二维矩阵，空间复杂度比较大，我们可以继续优化。

观察递推代码可以发现，递推代码中dp[i-1][j]、dp[i-1][j-nums[i]]被频繁使用，也就是说，当前行的递推计算仅取决于上一行的这两个位置的数，其他数字不要也可以，但是上一行却占了一整行的空间。

我们可以把dp[n][target+1]给压缩成dp[target+1]（可以理解成纵向压扁），但需要从后往前更新。

因为只有倒序循环，计算dp[i][j]的时候dp[i-1][j-nums[i]]才没有被覆盖（空间优化后，只剩一行了），上述代码里的dp[j-t]才是正确的dp[i-1][j-nums[i]]（因为dp[i-1][j-nums[i]]一定在dp[i-1][j]的前面）。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int max = Arrays.stream(nums).max().getAsInt();
        if (sum % 2 == 1) return false;
        int target = sum / 2, n = nums.length;
        if (max > target) return false;
        boolean[] dp = new boolean[target+1];
        // 第一件物品选与不选
        dp[0] = true;
        dp[nums[0]] = true;
        for (int i = 1; i < n; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i]) {
                    // 两种情况有一种为true的话便成立
                    dp[j] = dp[j]|dp[j-nums[i]];
                } else { // else就可以省略掉了
                    dp[j] = dp[j];
                }
            }
        }
        return dp[target];
    }
}

优化前：

优化后：

第二题：目标和（力扣494）（01背包组合问题）

暴力搜索

遇到这种01背包组合问题，最简单的方法就是暴力搜，Java代码如下：

class Solution {
    int ans = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return ans;
    }
    void dfs(int[] nums, int target, int i, int cur) {
        // 只有i为nums.length的时候才返回，因为每个元素都需要考虑
        if (i == nums.length) { 
            ans += cur == target ? 1 : 0;
            return;
        }
        dfs(nums, target, i + 1, cur + nums[i]);
        dfs(nums, target, i + 1, cur - nums[i]);
    }
}

记忆化搜索

不难发现，在 DFS 的函数签名中只有「数值下标 i」和「当前结算结果 cur」为可变参数，考虑将其作为记忆化容器的两个维度，返回值作为记忆化容器的记录值。

由于 cur 存在负权值，为了方便，我们这里不设计成静态数组，而是使用「哈希表」进行记录。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }
    Map<String, Integer> cache = new HashMap<>();
    int dfs(int[] nums, int target, int i, int cur) {
        // 二元组转化成字符串进行存储
        String key = i + "_" + cur;
        if (cache.containsKey(key)) return cache.get(key);
        if (i == nums.length) {
            cache.put(key, cur == target ? 1 : 0);
            return cache.get(key);
        }
        int left = dfs(nums, target, i + 1, cur + nums[i]);
        int right = dfs(nums, target, i + 1, cur - nums[i]);
        cache.put(key, left + right);
        return cache.get(key);
    }
}

动态规划

这道题用动态规划不太好做其实

在【416.分割等和子集】这道题中，要求的输出结果就是boolean值，因此我们定义的dp数组只需要记录T/F即可，但是这道题要求返回结果是方法数，那么我们dp数组需要记录的数据就是具体的方法数。

搞清楚需要输出的结果后，就可以来想办法画一个表格，也就是定义dp数组的含义。根据背包问题的经验，可以将dp[i][j]定义为从数组nums中 0 - i 的元素进行加减可以得到 j 的方法数量。

搞清楚状态以后，我们就可以根据状态去考虑如何根据子问题的转移从而得到整体的解。这道题的关键不是nums[i]的选与不选，而是nums[i]是加还是减，那么我们就可以将方程定义为：

dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

可以理解为nums[i]这个元素我可以执行加，还可以执行减，那么我dp[i][j]的结果值就是加/减之后对应位置的和。

初始状态：dp[0][nums[0]] = dp[0][-nums[0]] = 1，这里有种特殊情况，就是如果nums[0]=0，那么dp[0][0] = 2，意思是有加和减两种情况。

然后，我们就可以进行愉快的递推了，最终dp[n-1][target]就是所求的结果。

class Solution {
     int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        // 绝对值范围超过了sum的绝对值范围则无法得到
        if (Math.abs(target) > Math.abs(sum)) return 0;
        int len = nums.length;
        // - 0 +
        int t = sum * 2 + 1;
        int[][] dp = new int[len][t];
        // 初始化
        if (nums[0] == 0) {
            dp[0][sum] = 2;
        } else {
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < t; j++) {
                // 边界
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < t ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[len - 1][sum + target];
    }
}

01背包最值问题

这一类问题是01背包最经典的问题，有时间再更。