0/1背包问题（分割等和子集&最后一块石头的重量&目标和&一和零）

分割等和子集

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

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集

方法一：DFS
我的方法（超时）

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    return dfs(nums, 0, 0, sum / 2);
}

public boolean dfs(int[] nums, int i, int partSum, int sum) {
    if (partSum == sum) {
        return true;
    }
    if (partSum > sum || i == nums.length) {
        return false;
    }
    return dfs(nums, i + 1, partSum + nums[i], sum) || dfs(nums, i + 1, partSum, sum);
}

改进：将数组排序，先考虑较大的元素，这样好剪枝

public boolean canPartition(int[] nums) {
    int sum = 0;
    Arrays.sort(nums);
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    return dfs(nums, nums.length - 1, 0, sum / 2);
}

public boolean dfs(int[] nums, int i, int partSum, int sum) {
    if (partSum == sum) {
        return true;
    }
    if (partSum > sum || i < 0 || nums[i] > sum) {
        return false;
    }
    return dfs(nums, i - 1, partSum + nums[i], sum) || dfs(nums, i - 1, partSum, sum);
}

方法二：动态规划
其实是背包问题

dp[i][j]表示从nums[0]到nums[i]中挑一些数，每个数最多用一次，能否使和为j

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    sum /= 2;
    boolean[][] dp = new boolean[nums.length][sum + 1];
    if (nums[0] <= sum) {
        //只考虑第一个数时，只有和为第一个数才为true
        dp[0][nums[0]] = true;
    }
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j <= sum; j++) {
            dp[i][j] = dp[i - 1][j];//不选择第nums[i]
            if (j - nums[i] >= 0) {
                //dp[i - 1][j - nums[i]]选择num[i]
                dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
            }
        }
    }
    return dp[nums.length - 1][sum];
}

空间优化：
填表的时候只用到了上一行，所以可压缩为一维数组

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    sum /= 2;
    boolean[] dp = new boolean[sum + 1];
    if (nums[0] <= sum) {
        dp[nums[0]] = true;
    }
    for (int i = 1; i < nums.length; i++) {
        //由于填表时用到了正上方和左上方的元素，为避免新的值覆盖了原有的值，所以从后往前遍历
        for (int j = sum; j >= 0; j--) {
            if (j - nums[i] >= 0) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
    }
    return dp[sum];
}

最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块** 最重的** 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
    最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

大根堆

public int lastStoneWeight(int[] stones) {
    Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
    for (int num : stones) {
        queue.add(num);
    }
    while (queue.size() > 1) {
        int num1 = queue.poll();
        int num2 = queue.poll();
        if (num1 != num2) {
            queue.add(num1 - num2);
        }
    }
    return queue.isEmpty() ? 0 : queue.poll();
}

最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
    最后，**最多只会剩下一块 **石头。返回此石头 **最小的可能重量 **。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

和等和分割子集类似
把问题转化成将石头分成两堆，使两堆差值最小，理想情况两堆重量一样，总之使每堆总重量约接近sum/2，即背包容量为sum/2

public int lastStoneWeightII(int[] stones) {
    int sum = Arrays.stream(stones).sum();
    int n = stones.length, m = sum / 2;
    // n + 1 避免处理i=0
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j - stones[i] >= 0) {
                dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    for (int i = m; i >= 0; i--) {
        // 抵消掉能放进背包的重量
        if (dp[n][i]) {
            return sum - 2 * i;
        }
    }
    // 不可能
    return -1; 
}

目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

方法一：回溯

private int res;

public int findTargetSumWays(int[] nums, int target) {
    dfs(nums, 0, target);
    return res;
}

private void dfs(int[] nums, int i, int target) {
    if (i == nums.length) {
        if (target == 0) {
            res++;
        }
        return;
    }
    dfs(nums, i + 1, target - nums[i]);
    dfs(nums, i + 1, target + nums[i]);
}

方法二：动态规划
个数字都有两种状态：被进行“+”， 或者被进行“-”，因此可以将数组分成A和B两个部分：
A部分的数字全部进行“+”操作，B部分的数字全部进行“-”操作。
设数组的和为sum，A部分的和为sumA，B部分的和为sumB
根据上面的分析，我们可以得出： sumA + sumB = sum (1)
同时有： sumA - sumB = target (2)
将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
即：sumA = (sum + target) / 2 ，自此，原问题可以转化为0-1背包问题：
有一些物品，第i个物品的重量为nums[i]， 背包的容量为sumA，问：有多少种方式将背包【恰好填满】
这里需要注意的是，由于每个数字都是非负整数，因此sumA, sumB, sum都是非负整数。
根据(3)， 2sumA一定为偶数(自然数的性质，2n是偶数)，因此sum + target也应该是偶数。如果计算出的sum + target不是偶数，则与推导过程矛盾，本题无解。

public int findTargetSumWays(int[] nums, int target) {
    int sum = Arrays.stream(nums).sum();
    if ((sum + target) % 2 != 0 || Math.abs(target) > sum) {
        return 0;
    }
    int n = nums.length, m = (sum + target) / 2;
    int[][] dp = new int[n + 1][m + 1];
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i + 1][j] = dp[i][j];
            if (j - nums[i] >= 0) {
                dp[i + 1][j] += dp[i][j - nums[i]];
            }
        }
    }
    return dp[n][m];
}

空间优化：

public int findTargetSumWays(int[] nums, int target) {
    int sum = Arrays.stream(nums).sum();
    if ((sum + target) % 2 != 0 || Math.abs(target) > sum) {
        return 0;
    }
    int n = nums.length, m = (sum + target) / 2;
    int[] dp = new int[m + 1];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = m; j >= 0; j--) {
            if (j - nums[i] >= 0) {
                dp[j] += dp[j - nums[i]];
            }
        }
    }
    return dp[m];
}

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

动态规划
把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。
动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。
定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。

public int findMaxForm(String[] strs, int m, int n) {
    int len = strs.length;
    int[][][] dp = new int[len + 1][m + 1][n + 1];
    for (int i = 0; i < len; i++) {
        int[] count = count(strs[i]);
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (j - count[0] >= 0 && k - count[1] >= 0) {
                    dp[i + 1][j][k] = Math.max(dp[i][j][k], dp[i][j - count[0]][k - count[1]] + 1);
                } else {
                    dp[i + 1][j][k] = dp[i][j][k];
                }
            }
        }
    }
    return dp[len][m][n];
}

private int[] count(String s) {
    int[] res = new int[2];
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') {
            res[0]++;
        } else {
            res[1]++;
        }
    }
    return res;
}

空间优化：

public int findMaxForm(String[] strs, int m, int n) {
    int len = strs.length;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < len; i++) {
        int[] count = count(strs[i]);
        for (int j = m; j >= 0; j--) {
            for (int k = n; k >= 0; k--) {
                if (j - count[0] >= 0 && k - count[1] >= 0) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
                }
            }
        }
    }
    return dp[m][n];
}

private int[] count(String s) {
    int[] res = new int[2];
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') {
            res[0]++;
        } else {
            res[1]++;
        }
    }
    return res;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 416. 分割等和子集（Python）
    题目 难度：★★★☆☆类型：数组方法：动态规划 力扣链接请移步本题传送门更多力扣中等题的解决方案请移步力扣中等题目...
    玖月晴阅读 1,275评论 0赞 0
  • 2020-08-11 分割等和子集
    题目描述 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意: 每...
    养企鹅菌阅读 487评论 0赞 0
  • 【Leetcode-416】动态规划-分割等和子集
    2020-10-11 打卡题-动态规划 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个...
    Murrey_Xiao阅读 653评论 0赞 0
  • T416、分割等和子集
    给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意:每个数组中的元素...
    上行彩虹人阅读 106评论 0赞 0
  • 分割等和子集
    题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例：输入...
    windUtterance阅读 351评论 0赞 0