背包问题
0-1背包（i代表的是0到i任取，有不放i状态和放i状态
dp[i][j]表示，背包容量为j，可从i种物品中任选。
- 价值总和最大是多少！！
确定递推公式
再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]，（放得下和放不下
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
遍历每个物品和每个背包容量，对于第i个物品和背包容量j，考虑以下两种情况：
- 如果第i个物品的重量大于背包容量j，则无法将其放入背包，此时最大价值为dp[i-1][j]。
- 如果第i个物品的重量小于等于背包容量j，则可以选择放入或不放入背包，取两种情况下的最大价值，即max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
-
使用一维数组（要倒序遍历，保证物品只能添加一次
-
分割等和字串（也是背包问题，target为总体之和除2
-
class Solution {public boolean canPartition(int[] nums) {if (nums == null || nums.length == 0) return false;int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0) return false;//目标为奇数返回falseint target=sum/2;int dpLen=target+1;//数组长度，为容量+1int[] dp=new int[dpLen];for(int i=0;i<nums.length;i++){//物品的遍历for(int j=target;j>=nums[i];j--){//背包遍历，j表示容量，nums[i]表示容量和价值dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}if(dp[target]==target) return true;}return false;} }
