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

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int n = Integer.parseInt(str[0]);//物品数量
        int vol = Integer.parseInt(str[1]);//背包体积
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i=1;i<=n;i++){
            str = sc.nextLine().split(" ");
            v[i] = Integer.parseInt(str[0]);//物品数量
            w[i] = Integer.parseInt(str[1]);//背包体积
        }
        //dp表示不考虑背包是否装满，最多能装多大价值的物品
        int[] dp = new int[vol+1];
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            //由于每个商品只能装一次，故使用倒叙
            for(int j=vol;j>=v[i];j--){
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[vol]);

        //dp2表示背包恰好装满时最多能装多大价值的物品
        int[] dp2 = new int[vol+1];
        Arrays.fill(dp2,Integer.MIN_VALUE);
        dp2[0]=0;
        for(int i=1;i<=n;i++)
            //由于每个物品只能装一次，故使用倒叙
            for(int j=vol;j>=v[i];j--){
                dp2[j]=Math.max(dp2[j],dp2[j-v[i]]+w[i]);//只有正好装满才会更新为正数，否则为负数
            }
        if(dp2[vol]<0)
            System.out.println(0);
        else
            System.out.println(dp2[vol]);




    }
}