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

import java.io.*; 
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split(" ");
        int num = Integer.parseInt(s[0]);
        int vtotal = Integer.parseInt(s[1]);
        int [][] arr = new int[num][2];
        for(int i=0;i<num;i++){
            s=br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(s[0]);
            arr[i][1] = Integer.parseInt(s[1]);
        }
        //求最大价值
        int [][] maxW= new int[num+1][vtotal+1];
        for(int i=1;i<=num;i++){
            for(int j=1;j<=vtotal;j++){
                if(arr[i-1][0]<=j){
                    maxW[i][j] = Math.max(maxW[i-1][j-arr[i-1][0]]+arr[i-1][1],maxW[i-1][j]);
                }
                else{
                    maxW[i][j] = maxW[i-1][j];
                }
            }
        }
        System.out.println(maxW[num][vtotal]);
        int [] dpw = new int [vtotal+1];
        Arrays.fill(dpw,Integer.MIN_VALUE);
        dpw[0] = 0;
        for(int i=1;i<=num;i++){
            for(int j=vtotal;j>=arr[i-1][0];j--){
                dpw[j] = Math.max(dpw[j-arr[i-1][0]]+arr[i-1][1],dpw[j]);
            }
        }
        if(dpw[vtotal]<0){
            dpw[vtotal]=0;
        }
        System.out.println(dpw[vtotal]);
    }
}