题解 | 【模板】01背包-Java

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];
    }
}