算法——动态规划：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];}
};