信息学奥赛一本通T1272-分组背包-题解（Java代码）

解题思路：跟01背包有点像，每一组都只能选择一个物品，那么i就代表这一组

                ，j代表背包容量，然后用k去遍历i这一组的所有的物品，取最大值

参考代码：

import java.util.Scanner;
import java.util.Vector;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt();// 背包容量
        int N = sc.nextInt();// 物品数量
        int T = sc.nextInt();// 最大组号

        int[] W = new int[N + 1];
        int[] C = new int[N + 1];
        int[][] Pi = new int[T + 1][N];//记录T个组的每一个物品的下标
        for (int i = 1; i <= N; i++) {
            W[i] = sc.nextInt();
            C[i] = sc.nextInt();
            int pi = sc.nextInt();
            for (int j = 0; j < Pi[pi].length; j++) {
                if (Pi[pi][j] == 0) {
                    Pi[pi][j] = i;
                    break;
                }
            }
        }

        int dp[] = new int[V + 1];
        //遍历每一组
        for (int i = 1; i <= T; i++) {
            for (int j = V; j >= 0; j--) {
                //遍历每一组的所有元素
                for (int k = 0; k < Pi[i].length; k++) {
                    if (Pi[i][k] == 0) {
                        continue;
                    }
                    //如果背包容量j大于等于i组下的第k个物品的重量
                    if (j >= W[Pi[i][k]]) {
                        //dp[j]为不选这个物品的情况
                        //dp[j - W[Pi[i][k]]]+ C[Pi[i][k]]选这个物品的情况
                        dp[j] = Math.max(dp[j], dp[j - W[Pi[i][k]]]
                                + C[Pi[i][k]]);
                    }

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

    }
}