【Hot100】LeetCode—416. 分割等和子集

---

题目

• 原题连接：416. 分割等和子集

---

1- 思路

理解为背包问题

• 思路： 能否将均分的子集理解为一个背包，比如对于 [1,5,11,5]，判断能否凑齐背包为 11 的容量
• 在本题中，背包中的物品是不可以重用的

1.定义 dp 数组

• dp[j] 代表容量为 j 的数组的最大价值，在本题中，容量就是价值。重量为 5 的石头，价值就是 5
• 可划分条件：dp[target] == target 也就是装满 target 的最大价值刚好是 target 这时候就可以划分

2.递推公式

• dp[j] = Math.max(dp[j],dp[j-weight[i]]+values[i]) ——> 在本题目中 weight 和 value 是一个东西

3.初始化

---

2- 实现

⭐152. 乘积最大子数组——题解思路

class Solution {
    public boolean canPartition(int[] nums) {
        // 求target
        int sum = 0;
        for(int s:nums){
            sum+=s;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;

        // 1. 定义dp
        int[] dp = new int[target+1];

        // 2. 递推公式
        // dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);

        // 3.初始化，都为 0
        dp[0] = 0;

        // 4. 先遍历物品，后遍历背包(逆序)
        for(int i = 0 ;i < nums.length;i++){
            for(int j = target;j>=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
                if(dp[j] == target){
                    return true;
                }
            }
        }
        return false;
    }
}

---

3- ACM 实现

public class splitNums {

    public static boolean splitNums(int[] nums){
        // 先求 target
        int len = nums.length;
        int sum = 0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%2==1) return false;
        int target = sum/2;

        // 1. 定义 dp 数组
        int[] dp = new int[target+1];

        // 2. 递推公式
        // dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
        dp[0] = 0;
        // 3.初始化
        // 4. 遍历顺序，先遍历物品后遍历背包
        for(int i = 0 ; i < nums.length;i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组长度");
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0 ; i < n ; i++){
            nums[i] = sc.nextInt();
        }
        System.out.println("结果是"+splitNums(nums));
    }
}

原文地址：https://blog.csdn.net/weixin_44382896/article/details/140639484

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！