416. 分割等和子集 1049.最后一块石头的重量II

分割等和子集

问题

正整数组合，分成两个元素之和相等的组合，可以输出ture不可以输出false。

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

先导思索

可以暴力搜索，用第一个元素和其他元素和比较和等不等，然后第一个和第二个元素的和 和其他元素和比，不断这样最后比完返回答案。

用背包问题解决的话，背包问题是一个有i个物品，j的背包负重，每个物品有对应的负重和价值。这里元素只可以使用一次是01背包，i个元素，每个元素有自己的值，不段排列组合i个元素，然后排列组合完看有没有相等值，然后ture或false？

思路

套入背包问题里来，负重是元素值，价值也为元素值，再利用一个特点，载重为sum/2的背包的最大重量和(最大和)是小于或者等于sum/2的(最大就是等于sum/2)，所以最后取最大值就可以判断能不能分割，=返回true，不=sum/2返回flase。

为啥可以把负重和价值都看成元素值？

（为啥可以把负重和价值都看成元素值？这点没想明白，不过在背包问题里，负重和价值好像确实也不是依附存在的）

为啥sum/2的负重，然后尽力装后的最大值是小于或等于sum/2的呢？

比如数组是【1, 5】，那么容量为(1+5)/2 = 3的背包最多能背的重量和是1，对应题目也就是不能分成相等的两堆。如果数组是【1, 2, 3】，那么容量为(1 + 2+ 3) /2的背包最多能背的重量和就是3，等于sum/2，对应的也就是能够分成相等的两堆。（来自SherlockShewhart）

递推公式

dp[j]等于装了负重为j的背包装满了后的最大载重。

dp[j]=max(dp[j],dp[j-nums[i]]+num[i]）

初始化

dp[0]=0，0负重值的背包装不了东西

// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);

总代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
 
        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        // 也可以使用库函数一步求和
        // int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;
        int target = sum / 2;
 
        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};

 

最后一块石头的重量II

问题

有一堆石头，每一块的重量都是正整数，每次都拿两块出来，重量分别为x，y，大的把小的磨没，自身重量减去小石头的重量，相等就同归于尽，求不断这样做后最后留下来的石头重量最小的重量是多少，全部没了就返回0.

范围 1 <= stones.length <= 30，1 <= stones[i] <= 1000

思路

套入背包问题，重量为重量，价值为重量。背包问题是求负重最大时候的最大价值的，以负重的最大重量和为界限分成两份尽力接近的重量和，然后大的减小的，这样最终留下的重量和就是最小的了。还要改一下，直接求这堆石头的最大重量和，然后分半，然后背包的j再带进去求，最后最大重量和减去背包问题求得的最大重量和就好。留下的就是结果。

递推公式

物品的重量为stones[i]，物品的价值也为stones[i]，dp[j]的意思是，j容量的背包装的下的最大重量。

dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

初始化

1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。

要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

vector<int> dp(15001, 0);

总代码

target对sum的取半是向下取整，意思就是dp[target]小于等于sum-dp[target]，所以

（sum-dp[target]）-dp[target]是最小重量和

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;
        for (int i = 0; i < stones.size(); i++) { // 遍历物品
            for (int j = target; j >= stones[i]; j--) { // 遍历背包
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};