题解 | 【模板】完全背包

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();//n and Volume
        // 这里我把价值和重量的字母正常写了，而非像题目那样有点反直觉
        int []v = new int [n]; //value
        int []w = new int [n]; //weight
        for (int i = 0; i < n; ++i) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        //dp[i]表示在容量为i时的最大价值
        //求解问题一
        int []dp1 = new int [V + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = w[i]; j <=V; ++j) {//完全背包是指物品不限量的情况下，此时可以升序遍历。限1件物品的时候需要降序遍历（后面的元素先改变而不影响前面的元素）。
                dp1[j] = Math.max(dp1[j - w[i]] + v[i], dp1[j]);
            }
        }

        // 求解问题二
        int []dp2 = new int [V + 1];
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = w[i]; j<=V; ++j) {
                dp2[j] = Math.max(dp2[j - w[i]] + v[i], dp2[j]);
            }
        }
        if (dp2[V] < 0)
            dp2[V] = 0;//无解

        System.out.println(dp1[V] + "\n" + dp2[V]);
    }
}