算法题之分割等和子集问题

算法题之分割等和子集问题

问题描述

问题分析

代码实现

//利用动态规划完成问题的求解(二维动态规划数组完成)
    public boolean canPartition(int[] nums) {
        //首先我们需要判断nums数组的长度是否 > 1
        if (nums.length < 2) return false;
        //进行求nums数组所有正整数的和
        int sum = 0;
        for (int num : nums) {
            sum = sum + num;
        }
        //判断sum是否为偶数
        if (sum % 2 != 0) return false;
        //若满足上述条件我们利用动态规划进行问题求解
        int target = sum / 2;
        int len = nums.length;
        boolean[][] dp = new boolean[len][target + 1];
        //进行dp数组若干情况的初始化
        for (int i = 0; i < len; i++) {
            dp[i][0] = true;
        }
        if (nums[0] <= target) dp[0][nums[0]] = true;

        //遍历数组:进行dp[i][j]值的更新
        for (int i = 1; i < len; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                }else {//nums[i] <= j
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                }
            }
        }
        //for循环遍历结束:返回dp[len][target]的值:即数组索引从0 ~ len,是否可以将数组分为两个子集,使得两个子集的元素和相等
        return dp[len - 1][target];
    }

最后

以上就是坚定日记本为你收集整理的算法题之分割等和子集问题的全部内容，希望文章能够帮你解决算法题之分割等和子集问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。