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

import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int V = in.nextInt();

    int[] v = new int[n+1];
    int[] w = new int[n+1];
    int[][] dp = new int[n+1][V+1];
    for(int i = 0;i< n;i++){
        v[i+1] = in.nextInt();
        w[i+1] = in.nextInt();
    }
    for(int i = 1;i<= n;i++){
        for(int j = 1;j <= V;j++){
            if(v[i] > j)dp[i][j] = dp[i-1][j];
            else{
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
    }
        System.out.println(dp[n][V]);
     int[] dp2=new int[V+1];
    Arrays.fill(dp2,Integer.MIN_VALUE);
    //没有物品时，价值为0
    dp2[0]=0;
    for(int i=1;i<=n;i++){
        //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
        for(int j=V;j>=v[i];j--){
            //状态转移，要么选择第i件物品，要么不选，取价值最大的
            dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j]);
        }
    }
    //如果小于0，说明不能从初始状态转移过来，无解
    if(dp2[V]<0){
        dp2[V]=0;
    }
    System.out.println(dp2[V]);
}

}