代码随想录训练营day35|46. 携带研究材料，416. 分割等和子集

46. 携带研究材料

思路：用一个数组来记录？dp[i]=带i件物品的最大价值

好吧，这里用的是一个二维数组dp[i][j]，表示从[0，i]的物间任选武平，能用容量为j的背包装下的最大价值
重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

先考虑从[0,0]区间内的物品，容量为0时无法装，价值为0，物品0占用空间为1，所以1及以后价值为15

再来看[0，1]区间内的物品。容量为1，2时价值为5，（此时不装物品1，延续dp[i-1][j]），容量为3时，价值为20（装了它背包剩余空间为j-3）剩余空间的最大价值是dp[i][j-weigh[j]]，

所以dp[i][j]有两种选择，要么不放第i件物品，价值是dp[i-1][j]；
要么放第i件物品，那剩余空间是j-weight[j]，该空间最大价值dp[i][j-weigh[j]]，加上value[i]。
dp[i][j]=max（dp[i-1][j]，dp[i][j-weight[i]+value[i]）

草，刚刚找了半个小时问题在哪里，原来是dp[i-1][j-weight[i]]+value[i]

滚动数组的写法

因为上一个二维数组的每一行其实都在用上一行的数据，所以可以直接写一个一维数组，不断更新它。
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
但要注意，现在第j列需要用到它左边的数，但需要的是没被覆盖过的数据，而不是已经装入物品的数据，所以遍历顺序应该从右向左

for(int j=m;j>=0;j--){        
if(j-weight[i]>=0)
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
else
    dp[j]=dp[j];
}

416. 分割等和子集

思路：肯定先剪枝啦，和为奇直接false。j代表当前的体积。i表示当前可以任选的元素有[0，i]。dp[i][j]表示当前选择的和

dp[i][j]有两种选择
dp[i][j]=dp[i-1][j];//不装第i个数
dp[i][j]=nums[i]+dp[i-1][j-1];装了第i个数。
但如何选择呢??
好吧是这样理解的：
背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。
所以每个地方只有选了max。背包空间为sum/2的地方才有可能装满
（超了的不会装进去）

		for(int i=1;i<n;i++){
            for(int j=1;j<sum/2+1;j++){
                if(j-nums[i]>=0){//能放nums[i]进来，则当前容量一定要比他大。
                    dp[i][j]=max(dp[i-1][j],nums[i]+dp[i-1][j-nums[i]]);
                }
                else
                    dp[i][j]=dp[i-1][j];
                if(dp[i][j]==sum/2)
                    return true;
            }
        }
        return false;