背包问题

0-1背包（i代表的是0到i任取，有不放i状态和放i状态

dp[i][j]表示，背包容量为j，可从i种物品中任选。

1. 价值总和最大是多少！！ 确定递推公式

再回顾一下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;//目标为奇数返回false
          int target=sum/2;
          int dpLen=target+1;//数组长度，为容量+1
          int[] 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;
      }
  }