acwing-4. 多重背包问题 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] w = new int[N + 1];
        int[] value = new int[N + 1];
        int[] nums = new int[N+1];
        for(int i = 1; i<= N; i++){
            w[i] = sc.nextInt();
            value[i] = sc.nextInt();
            nums[i] = sc.nextInt();
        }
        int res = getMaxValue(N, w, value, V, nums);
        System.out.print(res);
    }
    
    public static int getMaxValue(int n, int[] w, int[] value, int V, int[] nums){
        // dp中存的是最大价值
        int[][] dp = new int[n + 1][V + 1];
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                for(int k = 0; k*w[i] <= j && k <= nums[i]; k++){
                   dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*w[i]] + k*value[i]);
                }
            }
        }
        return dp[n][V];
    }
}