// 0-1背包问题母代码(二维)
public int bags(){
  int[] weight = new int[]{1,3,4}; // 各个物品的重量
  int[] value = new int[]{15,20,30}; // 各个物品对应的价值
  int bagWeight = 4; // 背包最大容量

  // 状态定义：dp[i][j]表示从0-i个物品中选择不超过重量j的物品的最大价值
  int[][] dp = new int[weight.length()+1][bagWeight+1];

  // 初始化：第一列都是0(背包重量为0时啥都翻不了，价值都为0)；第一行表示只选0号物品时的最大价值(首先要保证能容纳下0号物品的重量)
  for(int j = weight[0]; j <= bagWeight ; j++){
    dp[0][j] = dp[0][j-weight[0]] + value[0];
  }

  // 遍历方向：当前状态只与正上方和左上方的那行相关
  for(int i = 1; i< weight.length(); i++){ // 遍历物品(第0个物品已经初始化了)
    for(int j = 0; j <= bagWeight; j++){ // 遍历背包容量
      if(j < weight[i]){ // 背包容量已经不足以放下第i个物品，因此最大价值就和上一个状态一致
        dp[i][j] = dp[i-1][j]; 
      }else{ 
        // 背包容量足够，可拿可不拿：拿了最大价值是前i-1个物品扣除第i个物品的 重量的最大价值加上i个物品的价值
        // 不拿就是前i-1个物品的最大价值,两者进行比较取较大的
        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
      }
    }
  }
  return dp[weight.length()-1][bagWeight];
}

public int bags(){
  int[] weight = new int[]{1,3,4}; // 各个物品的重量
  int[] value = new int[]{15,20,30}; // 各个物品对应的价值
  int bagWeight = 4; // 背包最大容量

  // 状态定义: dp[j]表示容量为j的背包能放下东西的最大价值。
  // 初始化: dp[0]=0
  int[] dp = new int[bagWeight+1];

  // dp[i][j] 都是通过上一行 dp[i-1][..] 转移过来的，之前的数据都不会再使用了。
  for(int i = 1; i< weight.length(); i++){ // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--){ // 逆向遍历是为了防止覆盖状态,j<=weight[i]时，dp[j]=dp[j]可以省略;也可以理解成防止重复添加数据
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); // 不取或者取第i个
    }
  }
  return dp[bagWeight];
}

  for(int i = 1; i< weight.length(); i++){ // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--){ // 逆向遍历是为了防止覆盖状态,j<=weight[i]时，dp[j]=dp[j]可以省略;也可以理解成防止重复添加数据
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); // 不取或者取第i个
    }
  }

// 先遍历物品，再遍历背包
// dp[i][j]表示从0-i个物品中选择不超过重量j的物品的最大价值
for(int i = 0; i < weight.size(); i++) { // 遍历物品
  for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  }
}