题解 | 【模板】完全背包

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int i = 0;i < T; i++){
            // 物品数量
            int n = in.nextInt();
            // 背包容量
            int m = in.nextInt();
            int[] w = new int[n];
            int[] v = new int[n];
            for(int j = 0; j < n; j++){
                w[j] = in.nextInt();
                v[j] = in.nextInt();
            }
            int[] dp = new int[m + 1];
            for(int j = 0; j < n; j++){
                // 这里不能像 01 那样倒着计算，因为涉及到物品个数无限的问题
                // 正序计算的话，会重复计算前面的物品
                for(int k = w[j]; k <= m; k++){
                    dp[k] = Math.max(dp[k], dp[k - w[j]] + v[j]);
                }
            }
            System.out.println(dp[m]);
        }
    }
}