题目描述

多重背包问题I（JAVA实现）

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        List<Integer> v = new ArrayList<>();
        List<Integer> w = new ArrayList<>();
        for(int i = 1;i <= N;i ++){
            int vi = sc.nextInt();
            int wi = sc.nextInt();
            int si = sc.nextInt();
            while(si-- > 0){
                v.add(vi); //转成0-1背包问题
                w.add(wi);
            }
        }
        int[] dp = new int[V + 1];
        for(int i = 0;i < v.size();i ++){
            for(int j = V;j >= v.get(i);j --){   //和0-1背包问题一样的  
                dp[j] = Math.max(dp[j],dp[j - v.get(i)] + w.get(i)); 
            }
        }
        System.out.println(dp[V]);
    }

}