题解 | 【模板】01背包

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();//n and Volume
        // 这里我把价值和重量的字母正常写了，而非像题目那样有点反直觉
        int []v=new int [n];//value
        int []w=new int [n];//weight
        for(int i=0;i<n;++i){
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        //dp[i]表示在容量为i时的最大价值
        //求解问题一
        int []dp1 = new int [V+1];
        for(int i=0;i<n;++i){
            for(int j=V;j>=w[i];--j){
                dp1[j] = Math.max(dp1[j-w[i]]+v[i], dp1[j]);
            }
        }

        // 求解问题二,从价值最大为1000,可以看出只有刚好装满才能在不累加int最小值的情况大于0.
        int []dp2 = new int [V+1];
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0;
        for(int i=0;i<n;++i){
            for(int j=V;j>=w[i];--j){
                dp2[j] = Math.max(dp2[j-w[i]]+v[i], dp2[j]);
            }
        }
        if(dp2[V] < 0)
            dp2[V] = 0;//无解

        System.out.println(dp1[V]+"\n"+dp2[V]);
    }
}