题目描述

blablabla

样例

import java.util.Scanner;

public class Main {
    static int N = 1010 ;
    static int[] v,w;
    static int n,V;
    static int[][] mem ;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        V = scanner.nextInt();
        v = new int[N];
        w = new int[N];
        mem = new int[N][N];
        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        System.out.println(dfs(1, V));
    }
    public static int dfs( int x,int syV){
        if (mem[x][syV] != 0) return mem[x][syV];
        int sum = 0;
        if (x > n) return 0;
        if (syV<v[x])  sum=dfs(x+1, syV);
        else {
             sum=Math.max(dfs(x+1, syV), dfs(x, syV-v[x])+w[x]);
        }
        mem[x][syV] = sum;
        return sum;
    }
}