题解 | 【模板】01背包

import java.util.*;

public class Main {
    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = scanner.nextInt();
        //存放体积
        int[] v = new int[n+1];
        //存放价值
        int[] w = new int[n+1];
        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        
        //dp1[i]表示不考虑是否装满，容量为i的情况下，最多装多大价值的物品
        int [] dp1 = new int [V+1];
        //i表示的是第几件物品，遍历1-n的物品，选择放不放
        for(int i =1;i<=n;i++) {
        	//倒序遍历存放的体积，防止重复计算
        	for(int j = V ;j>=v[i];j--) {
        		//选与不选各自价值的最大值
        		dp1[j] = Math.max(dp1[j], dp1[j-v[i]]+w[i]);
        	}
        }
        System.out.println(dp1[V]);
        
        //dp2[i]表示的是背包恰好装满时，容量恰好为i的情况下，最多装多大的价值
        int []dp2 = new int [V+1];//V+1个数组数字，从0开始，下标正好是0-V
        //填充数组为最小值不可取
        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--) {
        		//状态转移
        		dp2[j]=Math.max(dp2[j-v[i]]+w[i], dp2[j]);
        	}
        }
        if(dp2[V]<0)
        	dp2[V]=0;
        
        System.out.println(dp2[V]);
	}
}