[416]. 分割等和子集

[416]. 分割等和子集

• • 题目
  • 算法设计：动态规划

 

---

题目

• 题目：[416]. 分割等和子集

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

---

算法设计：动态规划

背包建模：

• 背包的容量是谁
• 背包的物品是谁，物品的成本、价值是多少
• 背包的选取方式是什么

问我们能否将一个数组分成两个「等和」子集。

问题等效于能否从数组中挑选若干个元素，使得元素总和等于所有元素总和的一半。

这道题如果抽象成「背包问题」的话，应该是：

• 背包容量是：$target=sum/2$
• 背包物品是：$数组元素$，每个数组元素的「价值」与「成本」都是其数值大小
• 背包选取方式是：求解将哪些物品装入背包 $恰好装满$

设计状态：

• dp[i][j]：对前 i 个物品，背包容量为 j 时，若 x 为 true，则恰好装满；否则不能恰好装满。

设计 base case：

• dp[0][...] = false：没有物品，不能装满
• dp[...][0] = false：背包没有容量，不能装满

设计最终状态：

• dp[N][sum/2]

设计状态转移方程，最终状态从哪里来：

• 不装第 N 种物品，dp[N][sum/2] = dp[N-1][sum/2]，来自上一件物品的处理结果
• 装入第 N 种物品，dp[N][sum/2] = dp[N-1][sum/2] || dp[N-1][j-nums[i]]，如果装了第 i 种物品，就要看背包剩余容量 j-nums[i] 是否能恰好转满

因为 dp[i][j] 只从 dp[i-1][j] 和 dp[i-1][j-w[i]] 而来，也就是说 [1....j] 这个数组是我们必须存的，但是 dp[1..i-1] 其实是不需要存的，只有 dp[i-1] 是有用的。

那可不可以设计一个一维数组 dp[1....j]，来代表 dp[i-1][1.....j] 呢?

• 可以的，简单来说，既然只需要上一行当前列和前面列的值，只用一个一维数组+倒推就可以了。

• 具体压缩过程，请看《动态规划二》的 01 背包。

01 背包状态压缩：

bool canPartition(vector<int> &nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 == 1)              // 如果是和为奇数显然无法分成两个等和子集
        return false;
    int target = sum / 2; 
    vector<int> dp(target + 1, 0); // dp[i]: 是否存在子集和为i
    dp[0] = true;                  // 初始化：target=0 不需要选择任何元素，所以是可以实现的
    
    for (int num : nums)
        for (int i = target; i >= num; i--)
            dp[i] = dp[i] || dp[i - num];
            
    return dp[target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14