LeetCode 416：分割等和子集（子集背包）

小半 • 2023年2月3日上午10:46 • 技术随笔 • 阅读 240

链接
题目：

方法：子集背包

思路：

题目可以转化为：能否从数组中找若干元素，使得它们的和为sum / 2。因为如果满足以上条件，剩下的元素和也为sum / 2 ！

dp定义：
dp[i][w] = x 表示，对于前 i 个物品（i 从 1 开始计数），当前背包的容量为 w时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。

最终求的是dp[N][sum/2] ；
base case
dp[…][0] = true 和 dp[0][…] = false
状态转移
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i-1][w]，继承之前的结果。

如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i-1][w-nums[i-1]]。

dp[i - 1][w-nums[i-1]] ：
	如果装了第 i 个物品，就要看背包的剩余重量 w- nums[i-1] 限制下是否能够被恰好装满。
	换句话说，如果 w - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，
	也可恰好装满 w的重量；否则的话，重量 w肯定是装不满的。

	由于 dp 数组定义中的 i 是从 1 开始计数，而数组索引是从 0 开始的，
	所以第 i 个物品的重量应该是 nums[i-1]，这一点不要搞混。

Java实现：

class Solution {
    public boolean canPartition(int[] nums) {
int sum=0;
        for(int k:nums){
            sum=sum+k;
        }
        if (sum % 2 != 0) return false;
        
        int n=nums.length;
        // dp[i][w]前i个物品，容量为w时，是否能装一半sum
        boolean[][] dp=new boolean[n+1][sum+1];
        // i从1开始，w从1开始
        //base case
        //dp[0][w] false;
        //dp[i][0]=true;
        for(int i=0;i<n;i++){
            dp[i][0]=true;
        }

        for(int i=1;i<=n;i++){
            for(int w=1;w<=sum/2;w++){
                if(w-nums[i-1]<0){ // 容量不够，不装, 取决于上次结果
                    dp[i][w]=dp[i-1][w];
                }else{ // 之前true，则为true
                    dp[i][w]=dp[i-1][w] || dp[i-1][w-nums[i-1]];
                }
            }
        }
        return dp[n][sum/2];
    }
}