题解 | 【模板】01背包

//java解决0-1背包问题
import java.util.Scanner; 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int N = in.nextInt();
        for(int i = 0; i < N; i++){
            int ob = in.nextInt();
            int vol = in.nextInt();
            List<int[]> list = new ArrayList<>();
            int[][] memo = new int[ob][vol + 1];
            for(int k = 0; k < memo.length; k++){
                Arrays.fill(memo[k], -1);
            }
            for(int j = 0; j < ob; j++){
                int a = in.nextInt();
                int b = in.nextInt();
                list.add(new int[]{a,b});
            }
            int value = dfs(ob - 1, vol, list, memo);
            System.out.println(value);
        }

    }
    public static int dfs(int i, int v, List<int[]> list, int[][] memo){
        if(i < 0){
            return 0;
        }
        if(memo[i][v] != -1){
            return memo[i][v];
        }
        if(list.get(i)[0] > v){
            return memo[i][v] = dfs(i - 1, v, list, memo);
        }
        return memo[i][v] = Math.max(dfs(i - 1, v - list.get(i)[0], list, memo) + list.get(i)[1], dfs(i - 1, v, list, memo));
    }
}