0. 动态规划五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

1. 完全背包问题

完全背包问题中，每个物品都有无数个，可以重复选择。

• 二维dp数组

  int[][] dp = new int[n][totalWeight+1];
  for(int i = 0; i<n; ++i) {
      for(int j = 0; j<= totalWeight; ++j) {
          if(j < weight[i])
              dp[i][j] = dp[i-1][j];
          else 
              // 01背包是dp[i-1][j-weight[i]]+value[i]，一个物品不能重复选
              dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight[i]]+value[i]);
      }
  }
  

• 一维dp数组：顺序遍历，允许同种物品被重复选择。

      int[] dp = new int[totalWeight+1];
      for(int i = 0; i<n; ++i) {
          for(int j = weight[i]; j<=totalWeight; ++j) {
              dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
          }
      }
  

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int totalWeight = scanner.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        
        for(int i = 0; i<n; ++i) {
            weight[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }
        
        int[] dp = new int[totalWeight+1];
        for(int i = 0; i<n; ++i) {
            // 顺序遍历，同一个物品可以重复选
            for(int j = weight[i]; j<=totalWeight; ++j) {
                dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
            }
        }
        
        System.out.println(dp[totalWeight]);
    }
}