01背包问题---二维
问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能使用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划5步：
1、dp[i][j]：从下标[0,i]的物品里任取，放到容量为j的背包中最大的价值总和
2、递推关系：如果不让物品i，此时最大价值总和是dp[i-1][j]，如果放入物品i，此时最大价值总和是dp[i-1][j-weight[i]]+value[i]，所以最大价值应该是两者的最大值dp=max{dp[i-1][j]，dp[i-1][j-weight[i]]+value[i]}；
3、初始化：由递推关系式可以知道，dp[i][j]由其上面的数组元素或者由其左上角数组元素决定，所以需要初始化dp[0][j]与dp[i][0]的所有元素。
4、遍历顺序：i表示物品，j表示背包，无论是背包先遍历还是物品先遍历，都能满足dp[i][j]由其上面的数组元素或者由其左上角数组元素决定这一条件，同时遍历顺序为从小到大。
5、打印数组：遇到问题可以打印数组。
01背包问题---一维
问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能使用一次，求解将哪些物品装入背包里物品价值总和最大。
思路：由二维求解可知，下一层的每个元素由上一层决定，所以可以用一维数组来表示，下一行未处理的数据就是上一行直接拷贝而得。
动态规划5步：
1、dp[i]：背包容量为i可装入物品价值总和最大为dp[i]；
2、递推关系：如果不放入物品，此时最大价值总和为dp[i]，这个表达式是从二维运算得到的在二维数组中不放物品时dp[i-1][j]，根据二维转为一维的规则，所以一维的是dp[i]，如果继续放入物品，最大价值总和为dp[i-1]+value[i];所以dp[i]=max{dp[i]，dp[i-weigh[i]]+value[i]}；
3、初始值：由递推关系可知dp[0]=0；
4、递推关系：因为此时是一维数组，所以应该先遍历物品，后遍历背包，同时因为每个物品只能放一次，所以，背包的遍历应该是由后向前遍历，不然从前向后遍历，后面的元素会使用到前面的元素，但是前面的元素已经改变了，不是上一层的元素了。
5、打印数组：在遇到问题时打印数组可以看到细节。
416. 分割等和子集
思路：
这道题如果所有元素的和为奇数，则不能等和分割。可以把nums数组当作物品，每一个元素的价值和重量都是nums[i]，如果背包的最大重量为所有元素和的一半，则可以实现等和分割。
代码：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;
vector<int> dp(10001,0);
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%2==1) return false;
int target=sum/2;
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]);
}
}
if(dp[target]==target)return true;
return false;
}
};
