题解 | #【模板】完全背包#

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

public class Main {
    public static void main(String[] args) {
        
        // 以下代码用于获取输入数据
        Scanner scan = new Scanner(System.in);
        String nV = scan.nextLine(); // 获取物品个数和背包体积
        int n = Integer.valueOf(nV.split(" ")[0]); // 获取背包个数
        int V = Integer.valueOf(nV.split(" ")[1]); // 获取背包体积
        int[] v = new int[n + 1]; // 定义一个整型数组，用于存放物品的体积
        int[] w = new int[n + 1]; // 定义一个整型数组，用于存放物品的重量
        String vw;
        for (int i = 1; i <= n; i++) {
            vw = scan.nextLine();
            v[i] = Integer.valueOf(vw.split(" ")[0]); // 第 i 种物品的体积
            w[i] = Integer.valueOf(vw.split(" ")[1]); // 第 i 种物品的重量
        }
        
        // 以下代码是完全背包问题的具体实现
        // 为了提高效率，1）求这个背包至多能装多大价值的物品    2）若背包恰好装满，求至多能装多大价值的物品
        // 以上两个问题同时进行求解，并且我们直接使用数组压缩的方式，而不再使用朴素算法
        // 事实上，问题一和问题二的区别仅仅是数组 dp 初始化的不同而已
        int[] dp1 = new int[V + 1];
        int[] dp2 = new int[V + 1];
        
        // 注意，dp2 用于存放的是第二问的状态表示，初始化时，所有 dp[i] 都置为 Integer.MIN_VALUE
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0; // 注意，当体积为 0 时，是合法的状态
        
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) { // 完全背包问题和01背包问题，在代码层面上的区别就是这一层循环的方向不一样
                dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + w[i]);
                dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
                if (dp2[j] < 0) {
                    // 如果 dp2[i] 小于 0，我们可以认为此时的 dp 不合法，即不能使背包恰好装满
                    dp2[j] = Integer.MIN_VALUE;
                }
            }
        }
        
        System.out.println(dp1[V]);
        System.out.println(dp2[V] == Integer.MIN_VALUE ? 0 : dp2[V]); // 别忘了判断当前 dp 是否合法
        return;
    }
}