题解 | #【模板】01背包#

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        
        int[] v = new int[n];
        int[] w = new int[n];
        
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        
        //用体积数作为下标, 可以找到体积数对应的价值
        int[] dp1 = new int[V+1];
        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 = V; j >= v[i]; j--){
                dp1[j] = Math.max(dp1[j], dp1[j-v[i]]+w[i]);
                dp2[j] = Math.max(dp2[j], dp2[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp1[V]);
        System.out.println(dp2[V] < 0 ? 0 : dp2[V]);
    }
}