【模板】01背包

import java.util.Scanner;

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 + 1]; // 物品体积（1-based索引）
        int[] w = new int[n + 1]; // 物品价值（1-based索引）

        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 1. 方案1：不要求装满背包，求最大价值
        int maxUnfilled = solveUnfilled(n, V, v, w);
        // 2. 方案2：要求恰好装满背包，求最大价值（无解输出0）
        int maxFilled = solveFilled(n, V, v, w);

        System.out.println(maxUnfilled);
        System.out.println(maxFilled);
        sc.close();
    }

    /**
     * 不要求装满背包的最大价值
     * 初始状态：dp[0...V] = 0（空背包价值为0，未装满也可从0开始累积）
     */
    private static int solveUnfilled(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];
        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 倒序遍历容量（避免重复选同一物品）
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        return dp[V];
    }

    /**
     * 要求恰好装满背包的最大价值
     * 初始状态：dp[0] = 0（容量0恰好装满时价值为0），dp[1...V] = -∞（初始标记为无法装满）
     */
    private static int solveFilled(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];
        // 初始化：除容量0外，其余均设为负无穷（表示无法装满）
        for (int j = 1; j <= V; j++) {
            dp[j] = Integer.MIN_VALUE;
        }

        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 倒序遍历容量
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        // 若最终容量V仍为负无穷，说明无法装满，返回0；否则返回dp[V]
        return dp[V] < 0 ? 0 : dp[V];
    }
}

import java.util.*;
public class  Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int bag = sc.nextInt();
        int[][] gift = new int[num][2];
        for (int i = 0; i < num; i++) {
            gift[i][0] = sc.nextInt();
            gift[i][1] = sc.nextInt();
        }
        System.out.println(getMaxValue(gift, bag));
        System.out.println(getfullbag(gift,bag));
    }
    private static int getMaxValue(int[][] gift, int bag ) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                if (j - gift[i - 1][0] >= 0 ) {
                    dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],
                                        dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
    private static int getfullbag(int[][] gift, int bag) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                int left = j - gift[i - 1][0] ;
                if (left >= 0 ) {
                    if(left > 0){
                        if(dp[i-1][left] == 0){
                            dp[i][j] = dp[i-1][j];
                        }else{
                            dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],dp[i - 1][j]);
                        }
                    }else{
                        dp[i][j] = Math.max(gift[i - 1][1],dp[i - 1][j]);
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
}