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

01 背包问题，利用一维滚动数组进行优化 初始化条件： 初始化为负无穷化代表不可能装满 背包的容量为0，也为装满了，是一种可行的情况，则初始化为0

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int V = reader.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            v[i] = reader.nextInt();
            w[i] = reader.nextInt();
        }
        int[] dp = new int[V + 1];
        Arrays.fill(dp, Integer.MIN_VALUE + 10001);
        dp[0] = 0;
        // init
        // dp[i][j] = dp[i - 1][j], dp[i - 1][j - v[i]]
        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]);
            }
        }
        int res = 0;
        for (int i = 1; i <= V; i++) {
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
        System.out.println(dp[V] > 0 ? dp[V]: 0);
    }
}