题目描述

blablabla

样例

import java.util.Scanner;

public class Main {
    static int[] v,w,s;
    static int NN = 1100;
    static int N ,V;
    static int[][] mem = new int[NN][NN];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        V = scanner.nextInt();
        v = new int[NN];
        w = new int[NN];
        s = new int[NN];
        int[][] f = new int[NN][NN];
        for (int i = 1; i <= N; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
            s[i] = scanner.nextInt();
        }
        //System.out.println(dfs(1, V));

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                for (int k = 0; k <= s[i] && v[i]*k <= j ; k++) {
                    f[i][j] = Math.max(f[i][j] ,f[i-1][j-v[i]*k]+w[i]*k);
                }
            }
        }
        System.out.println(f[N][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{
            for (int i = 0; i <= s[x] && i*v[x]<=syV ; i++) {
                sum= Math.max(dfs(x, syV-(v[x]*i)) +w[x]*i ,dfs(x+1,syV));
            }
        }
        mem[x][syV] = sum;
        return sum;
    }
}

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla