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

╰+哭是因爲堅強的太久メ 2024-04-07 14:13 22阅读 0赞

[链接][Link 1]  
**题目**：  
![在这里插入图片描述][382c34bedb7f4ae4b9c23d17565b38e0.png]

### 方法：子集背包 ###

#### 思路： ####

题目可以转化为：能否从数组中找若干元素，使得它们的和为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];
        }
    }

**区别0-1背包**：  
0-1背包中，dp\[N\]\[W\] 是对于前 N 个物品，背包容量为W时，可以放的最大价值 ；  
子集背包中，dp\[i\]\[w\]是对于前 i 个物品，背包容量为 w时，是否可以将背包装满；

[Link 1]: https://leetcode.cn/problems/partition-equal-subset-sum/
[382c34bedb7f4ae4b9c23d17565b38e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8a7ec2bd16e2428bb530e3db826ec8e8.png