lt.416. 分割等和子集

[案例需求]

[思路分析一, 动态规划法]

[代码实现]

class Solution {
    public boolean canPartition(int[] nums) {
       
        // 背包的体积为Sum/2;
        // 背包要放入的商品(集合中的元素)重量为 元素的数值, 价值也为元素的数值;
        // 背包正好装满, 说明找到了总和为 Sum / 2的子集;
        // 背包中每一个元素是不可重复放入的

        //1. 确定DP数组以及下标的含义
        //0-1背包问题, dp[i][j], 0~i-1编号的物品放入到容量为j的背包中得到的最大价值
        // 本题: dp[j] 表示背包容量为j, 最大可以凑成j的子集的总和为dp[j]
        int sum = 0;
        int n = nums.length;

       int target = 0;

        for(int x : nums){sum += x;}
        if(sum % 2 != 0)return false;
        
        target = sum / 2;
        
        int[] dp = new int[sum / 2 + 1];
        //2. 确定递推公式
        //0,1背包:  dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        //dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        for(int i = 0; i < n; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[target] == target;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

lt.1049. 最后一块石头的重量 II

[案例需求]

[思路分析]

[代码实现]

1