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

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//物品数量
        int v = input.nextInt();//背包容量
        int[] vol = new int[n + 1]; //体积
        int[] val = new int[n + 1]; //价值
        for (int i = 0; i < n; i++) {
            vol[i + 1] = input.nextInt();
            val[i + 1] = input.nextInt();
        }
        
        //求解问题1：
        //01背包问题，dp[i] 表示背包容量为i时能放的最大价值。
        //对每个物品进行遍历，放不下的时候继承之前的，放得下的时候进行判断，如果放进去，总价值会不会比同容量的其他情况大
        //如果更大，就放进去。
        //最后的dp【v】就是想要的结果
        int[] dp = new int[v + 1];
        for (int i = 1; i <= n; i++) {
            //从1开始，且数组长度为i+1，既是防止数组越界，又是将默认的0作为初始状态
            for (int j = v; j >= vol[i]; j--) {              
                dp[j] = Math.max(dp[j], dp[j - vol[i]] + val[i]);
            }
        }
        System.out.println(dp[v]);
        
        //求解问题2：
        //思路：要么在将背包装满的各种可能里找最大的，要么在价值从大到小的可能中找第一个能装满的。
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        //将dp【0】置为0， 将其余的置为负数极限
        //这是为了恰好装满的条件，
        //这样可以保证，如果到容量为v时不是正好装满，就一定时INF + maxVal，小于零
        for (int i = 1; i <= n; i++) {
            for (int j = v; j >= vol[i]; j--) {              
                dp[j] = Math.max(dp[j], dp[j - vol[i]] + val[i]);
            }
        }
        if(dp[v] < 0){
            dp[v] = 0;
        }
        System.out.println(dp[v]);
        
    }
}