Java 代码

import java.util.Scanner;

public class Main {


    //分组背包：N组物品，每组只能选一个
    //状态表示：dp[i][j]，在背包承重为j的状态下，前i组中选择的最大价值
    //dp[i][j]的状态有：不选i组、选i组第一个、第二个...
    //dp[i][j] = dp[i - 1][j]、dp[i][j - v[i][1]] + w[i][1]、dp[i][j - v[i][2]] + w[i][2]
    //dp[i][j] = max(dp[i - 1][j], max(dp[i][j - v[i][k]] + w[i][k]))



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   //组数
        int V = sc.nextInt();   //容量
        int[] s = new int[102];
        int[][] v = new int[102][102], w = new int[102][102];
        for(int i = 1; i <= N; i++) {
            s[i] = sc.nextInt();
            for(int j = 1; j <= s[i]; j++) {
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

        //状态表示：dp[i][j] = max(dp[i - 1][j], max(dp[i - 1][j - v[i][k] + w[i][k]) )
        //dp[j] = max( dp[j], max(dp[j - v[i][k] + w[i][k]) )
        int[] dp = new int[V + 2];
        for(int i = 1; i <= N; i++) {
            for(int j = V; j > 0; j--) {
                for(int k = 1; k <= s[i]; k++) {
                    if(j >= v[i][k])
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
                }
            }
        }
        System.out.print(dp[V]);
    }
}