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

import java.util.Scanner;
import java.util.*;
//dp[i][j]表示从i个物品中选
//总体积不超过j的最大价值和

public class Main {
    static int N = 1010;
    static int n,V; //总数、总体积
    static int[] v = new int[N]; //表示体积
    static int[] w = new int[N];  //表示价值
    static int[][] dp = new int[N][N]; 

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            n = in.nextInt();
            V = in.nextInt();
            //读入数据 ,从1开始读入，创建虚拟节点
            for(int i=1;i<=n;i++){
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }
           
           //1.解决第一问
           //1.初始化,虚拟节点初始化为0即可
           //2.填表
           for(int i =1;i<=n;i++){
            for(int j=1;j<=V;j++){
                //1.不选第i个物品的价值
                dp[i][j] = dp[i-1][j]; //价值与前一个相同
                //2.选第i个物品价值，需要判断j-v[i] 是否还能装得下,
                //取两种情况最大值
                if(j>=v[i]) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]] +w[i]);
            }
           }
           System.out.println(dp[n][V]); //输出结果
           //解决第二问，先清空dp表
          for(int i=0;i<=n;i++){
            for(int j=0;j<=V;j++){
                dp[i][j] = 0;
                
            }
          }

           //1.初始化,上面的虚拟节点初始化为-1，因为不存在垓解
           for(int i=1;i<=V;i++) dp[0][i] = -1;

           //2.填表
            for(int i =1;i<=n;i++){
            for(int j=1;j<=V;j++){
                //1.不选第i个物品的价值
                dp[i][j] = dp[i-1][j]; //价值与前一个相同
                //2.选第i个物品价值，需要判断j-v[i] 是否还能装得下,
                //并且还要判断dp[i-1][j-v[i]] 是否有解
                if(j>=v[i] &&dp[i-1][j-v[i]] !=-1) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]] +w[i]);
            }
           }
           //输出第二问的解，需要判断是否存在
           if(dp[n][V]==-1){
            System.out.println(0);
           }else{
            System.out.println(dp[n][V]); 
           }
          


            
        }
    }
}