面试算法101:分割等和子集

发布时间:2024年01月08日

题目

给定一个非空的正整数数组,请判断能否将这些数字分成和相等的两部分。例如,如果输入数组为[3,4,1],将这些数字分成[3,1]和[4]两部分,它们的和相等,因此输出true;如果输入数组为[1,2,3,5],则不能将这些数字分成和相等的两部分,因此输出false。

分析

如果能够将数组中的数字分成和相等的两部分,那么数组中所有数字的和(记为sum)应该是一个偶数。也可以换一个角度来描述这个问题:能否从数组中选出若干数字,使它们的和等于sum/2(将sum/2记为t)。如果将数组中的每个数字看成物品的重量,也可以这样描述这个问题:能否选择若干物品,使它们刚好放满一个容量为t的背包?由于每个物品(数字)最多只能选择一次,因此这是一个0-1背包问题。(本题一共两个背包)
用函数f(i,j)表示能否从前i个物品(物品标号分别为0,1,…,i-1)中选择若干物品放满容量为j的背包。如果总共有n个物品,背包的容量为t,那么f(n,t)就是问题的解。
当判断能否从前i个物品中选择若干物品放满容量为j的背包时,对标号为i-1的物品有两个选择。一个选择是将标号为i-1的物品放入背包中,如果能从前i-1个物品(物品标号分别为0,1,…,i-2)中选择若干物品放满容量为j-nums[i-1]的背包(即f(i-1,j-nums[i-1])为true),那么f(i,j)就为true。另一个选择是不将标号为i-1的物品放入背包中,如果从前i-1个物品中选择若干物品放满容量为j的背包(即f(i-1,j)为true),那么f(i,j)也为true。

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 5};
        boolean result = canPartition(nums);
        System.out.println(result);
    }

	// 本题一共两个背包
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 == 1) {
            return false;
        }

        // 其中一些数字之和为sum/2,则能将所有数字分成和相等的两部分
        // 则问题转化:能否从nums中选出一些数字,使这些数字之和为sum/2
        return subsetSum(nums, sum / 2);
    }

    private static boolean subsetSum(int[] nums, int target) {
        Boolean[][] dp = new Boolean[nums.length + 1][target + 1];
        return helper(nums, dp, nums.length, target);
    }

    private static boolean helper(int[] nums, Boolean[][] dp, int i, int j) {
        if (dp[i][j] == null) {
            if (j == 0) {
                dp[i][j] = true;
            }
            else if (i == 0) {
                dp[i][j] = false;
            }
            else {
                dp[i][j] = helper(nums, dp, i - 1, j);// 不选择元素nums[i-1];
                if (!dp[i][j] && j >= nums[i - 1]) {
                    dp[i][j] = helper(nums, dp, i - 1, j - nums[i - 1]);// 选择元素nums[i-1];
                }
            }
        }

        return dp[i][j];
    }
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135461973
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。