题目描述

blablabla

样例

blablabla

算法1

Java 代码

import java.util.*;
import java.io.*;

public class Main{
    private static int N;
    private static int V;
    private static int[] dp;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]); // 物品组数
        V = Integer.parseInt(s1[1]); // 总体积
        dp = new int[V+1];  // 前N个物品，总体积是V的情况下总价值最大
        int maxV = 105;
        int maxN = 105;
        int[] dp = new int[maxV];
        int[] v = new int[maxN];
        int[] w = new int[maxN];

        for (int i=1 ; i <= N ; i++){ // 遍历所有组
            String[] num = read.readLine().split("\\s+");
            int M = Integer.valueOf(num[0]);
            for (int j = 0; j < M; j++) { 
                String[] ss = read.readLine().split("\\s+");
                v[j] = Integer.valueOf(ss[0]);
                w[j] = Integer.valueOf(ss[1]);
            }
            for (int j = V; j >= 0; j--) { // 遍历所有体积
                for (int k = 0; k < M; k++) { //所有的j属于组i的选择
                    if (j >= v[k]) {
                        dp[j] = Math.max(dp[j], dp[j - v[k]] + w[k]);
                    }
                }
            }
        }

        System.out.println(dp[V]);

    }
}