分割等和子集

分割等和子集 - 力扣（LeetCode）

三刷，虽然没有用01背包解决，但是却是使用到了之前刷蓝桥杯的时候学到的一种方式。下面附上两种dp方法：

bool类型dp：

比较好理解，对于新手而言，动态规划其实就是找规律，将重复计算的结果存下来，下次就不用计算了，直接用就行。dp 是一个布尔类型的动态规划数组，用于记录对于每个可能的和（从 0 到 total），是否存在一个子集能够达到这个和。 即，前i个能否恰好凑出一个j，如果可以，那就是true，反之就是false。

bool canPartition(vector& nums)
    {   
        int sum=0;
        for(int i=0;idp(total+1,false);
        dp[0]=true;
        for(int i=0;i=nums[i];j--)
            {
                if(j==nums[i])  dp[j]=true;
                else    dp[j]=dp[j]|dp[j-nums[i]];   
            }
        }
        return dp[total];
    }

01背包：

分成两个集合，那么相当于提取数据，一个是取，一个是不取 如果看做是背包问题的话，相当于一个容积为n，要取价值为总价值一半的情况 ！！！太妙了！！！价值和重量都为对应值，那么背包装满之后的总价值应该也是背包总容积！！！

二维：

bool canPartition(vector& nums) {
        
        int sum=0;
        for(int i=0;i0;j--)
            {
                if(j-nums[i]<0) dp[j]=dp[j];
                else    dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);          
            }
        if(dp[sum]==sum) return true;
        return false;
    }

一维：

bool canPartition(vector& nums)
{
	//这里难在转换成01背包 
	//这里的nums直接充当3个：val size 物品
	const int N = 100 * 200 / 2 + 3;
	int dp[N] = { 0 };
	int sum = 0;
	for (int i = 0; i < nums.size(); i++)	sum += nums[i];
	if (sum % 2 == 1)	return false;	//奇数，不可能
	int maxsize = sum / 2;
	for (int j = nums[0]; j <= maxsize; j++)
		dp[j] = nums[0];
	for (int i = 1; i < nums.size(); i++)
		for (int j = maxsize; j >=nums[i] ; j--)	//这道题就是判断能不能恰好把背包装满，所以才把sum/2作为maxsize
		{
			dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
		}
	if (dp[maxsize] == maxsize)	return true;
	return false;
}