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

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//物品数量
        int v = input.nextInt();//背包容量
        int[] vol = new int[n + 1]; //体积
        int[] val = new int[n + 1]; //价值
        for (int i = 0; i < n; i++) {
            vol[i + 1] = input.nextInt();
            val[i + 1] = input.nextInt();
        }
        
        int[] dp = new int[v+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= v; j++){
                if(j >= vol[i]){
                    //无限背包和01背包基本类似，区别就在于物品是否唯一，
                    //如果物品唯一，就从后向前填，这样每次值的更新都是基于没放该物品的情况，相当于只放了一件
                    //如果物品不唯一，就从前向后填，这样如果容量足以放重复的物品时，会基于前面放过的情况累加，相当于放了多件
                    dp[j] = Math.max(dp[j], dp[j - vol[i]] + val[i]);
                }
            }
        }
        System.out.println(dp[v]);
        
        Arrays.fill(dp,Integer.MIN_VALUE);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= v; j++){
                if(j >= vol[i]){
                    dp[j] = Math.max(dp[j], dp[j - vol[i]] + val[i]);
                }
            }
        }
        if(dp[v]<0){
            dp[v] = 0;
        }
        System.out.println(dp[v]);
    }
}