算法——动态规划：01背包

原始01背包见下面这篇文章：http://t.csdnimg.cn/a1kCL

01背包的变种：. - 力扣（LeetCode）

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

简化一下题目意思，即在一个数组中需要找若干个数，使这些数之和等于数组所有数据之和的一半。显然如果数组所有元素数据之和为奇数则必不可能找到。

与01背包问题类似，01背包问题的核心是在有限体积的背包内放入价值最大的物品；

dp[i][j]的定义为，从0到i这个范围内物品体积为j所能产生的最大价值。

状态变量：f[i][j]表示前i件物品放入容量为j的背包的最大价值

当前容量为j，我们要考虑第i件物品能否放入？是否放入？

如果当前背包容量j<v[i],不能放入，则f[i][j]=f[i-1][j]
如果当前背包容量j>=v[i]，能放入但是要比较代价
2.1 如果第i件物品不放入背包，则f[i][j]=f[i-1][j]
2.2 如果第i件物品放入背包，则f[i][j]=f[i-1][j-v[i]]+w[i]

本题也类似，只是条件不是找到价值最大的，而是价值恰好等于目标值的若干个数。

dp[i][j]的定义为：从0到i范围内是否存在某几个数使这些数字之和恰好等于j；

状态转移方程为：如果0到i-1内存在和为j的数，则0到i之间也必然存在。

或者如果由当前目标j减去当前所在的数组数据nums[i]，若0到i-1范围内存在和为j-nums[i]的数，则加上当前数据正好和为j，满足条件。

否则不存在。

核心代码为：

if(dp[i-1][j]||(nums[i]<=j&&dp[i-1][j-nums[i]]))

                dp[i][j]=true;

需要注意的是，最开始初始化时，dp[0][i]需要找到一个i等于数组第一个数字numd[0]，该dp[0][i]为true，其余均为false，表示0到0范围内不存在该数字。

初始化时dp[i][0]需要全部初始化为true，否则比如说第二个数字为2,2-2等于0，其实范围内出现了2，则一定满足条件。但是若dp[i][0]值为false反而会出错。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i=0;i<nums.size();i++)
        sum+=nums[i];
        if(sum%2==1)return false;
        vector<vector<bool>>dp(nums.size());
        int target=(sum>>1);
        for(int i=0;i<dp.size();i++)
        {
            dp[i].resize(target+1);
            for(int j=0;j<=target;j++)
            {
                dp[i][j]=false;
            }
        }
        for(int i=0;i<=target;i++)
        {
            if(nums[0]==i)
            {
                dp[0][i]=true;
                break;
            }
        }
        for(int i=0;i<nums.size();i++)
        dp[i][0]=true;
        for(int i=1;i<nums.size();i++)
        {
            for(int j=1;j<=target;j++)
            {
                if(dp[i-1][j]||(nums[i]<=j&&dp[i-1][j-nums[i]]))
                dp[i][j]=true;
            }
        }
        return dp[nums.size()-1][target];
    }
};