题解 | 【模板】01背包

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Stream;

/**
 * @author zengxiangbao
 * @date 2025/10/9 14:23
 * @description BGN70 【模板】01背包
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] w = new int[n + 1], v = new int[n + 1];
	  	//dp[][]是求解经典的背包问题（模板），dp2[][]是求解有恰好装满约束的变体问题
        int[][] dp = new int[n + 1][k + 1], dp2 = new int[n + 1][k + 1];
		
	  	//对于dp2[][]其实理解为遍历到i, 剩余容量j装满所能得到的最大值，那么原先的状态转移方程仍然是正确的，所以我想的是改变初始状态来得到正确的值，问题是我不知道怎么从逻辑的角度去理解这个问题并得到正确的初始条件。我的理解是只有恰好装满的情况能访问到dp[i][0], 其他情况只能访问到i = 0, 或者j - w[i] < 0结束。所以初始化除去j == 0的所有情况为Integer.MIN_VALUE,这样无法恰好装满的dp[i][j]因为一定访问不到dp[i][0]就会加上Integer.MIN_VALUE而小于0。但是因为是单纯从循环的角度理解，需要考虑较多的边界条件，所以......
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp2[i][j] = j == 0 ? 0 : Integer.MIN_VALUE;
            }
        }

        boolean flag = false;
        int result = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
            for (int j = 0; j <= k; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], j - w[i] >= 0 ? dp[i - 1][j - w[i]] + v[i] : 0);
			  	//处理j越界也设置为Integer.MIN_VALUE
                dp2[i][j] = Math.max(dp2[i - 1][j], j - w[i] >= 0 ? dp2[i - 1][j - w[i]] + v[i] : Integer.MIN_VALUE);
                if (j == k) {
                    result = Math.max(result, dp2[i][j]);
                }
            }
        }
        System.out.println(dp[n][k] + "\n" + (Math.max(result, 0))) ;
    }
	
  
//    下面是从dfs()解决第二问dfs(w, v, i, j)表示遍历到i个物品, 剩余容量为j且恰好装满的所能获得的最大值（和dp2[i][j]一样），这个比较好理解，但是时间复杂度为O(2 ^ n),对比dp的o(n * k)要高，需要使用记忆化搜索（cache），这实际是一个后续遍历，直接dfs结束把结果存int[][] cache就行了，变成o(n * k)
  
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt(), k = in.nextInt();
//        int[] w = new int[n + 1], v = new int[n + 1];
////        int[][] dp = new int[n + 1][k + 1];
//
//        for (int i = 1; i <= n; i++) {
//            w[i] = in.nextInt();
//            v[i] = in.nextInt();
//        }
//
//        int result;
//        System.out.println((result = dfs(w, v, n, k)) > -1 ? result : 0);
//
//    }
//
//    public static int dfs(int[] w, int[] v, int i, int j) {
//        if (j == 0) return 0;
//        if (j < 0) return -1;
//        if (i == -1) return -1;
//
//        int tmp;
//        return Math.max(dfs(w, v, i - 1, j), (tmp = dfs(w, v, i - 1, j - w[i])) > -1 ? tmp + v[i] : -1);
//
//    }
}