题解 | 购物单

import java.util.Scanner;
import java.util.HashMap;
import java.util.List; 
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int budget = in.nextInt();
        int n = in.nextInt();

        // 存储商品信息
        int[] prices = new int[n + 1];
        int[] satisfactions = new int[n + 1];
        int[] mainIds = new int[n + 1];

        // 存储主件对应的附件列表
        HashMap<Integer, List<Integer>> attachments = new HashMap<>();

        // 读取数据
        for (int i = 1; i <= n; i++) {
            prices[i] = in.nextInt();
            int importance = in.nextInt();
            mainIds[i] = in.nextInt();
            satisfactions[i] = prices[i] * importance;

            if (mainIds[i] > 0) {
                attachments.computeIfAbsent(mainIds[i], k -> new ArrayList<>()).add(i);
            }
        }

        // DP数组
        int[] dp = new int[budget + 1];

        // 处理每个商品
        for (int i = 1; i <= n; i++) {
            // 只处理主件，附件会在其主件中处理
            if (mainIds[i] != 0) continue;

            List<int[]> combinations = new ArrayList<>();

            // 主件信息
            int mainPrice = prices[i];
            int mainSatisfaction = satisfactions[i];

            // 组合1: 只买主件
            combinations.add(new int[] {mainPrice, mainSatisfaction});

            // 获取附件
            List<Integer> attList = attachments.get(i);
            if (attList != null) {
                int attCount = attList.size();

                if (attCount >= 1) {
                    int att1 = attList.get(0);
                    // 组合2: 主件 + 附件1
                    combinations.add(new int[] {
                                         mainPrice + prices[att1],
                                         mainSatisfaction + satisfactions[att1]
                                     });

                    if (attCount >= 2) {
                        int att2 = attList.get(1);
                        // 组合3: 主件 + 附件2
                        combinations.add(new int[] {
                                             mainPrice + prices[att2],
                                             mainSatisfaction + satisfactions[att2]
                                         });

                        // 组合4: 主件 + 附件1 + 附件2
                        combinations.add(new int[] {
                                             mainPrice + prices[att1] + prices[att2],
                                             mainSatisfaction + satisfactions[att1] + satisfactions[att2]
                                         });
                    }
                }
            }

            // 分组背包DP
            for (int j = budget; j >= 0; j--) {
                for (int[] comb : combinations) {
                    if (j >= comb[0]) {
                        dp[j] = Math.max(dp[j], dp[j - comb[0]] + comb[1]);
                    }
                }
            }
        }

        System.out.println(dp[budget]);
        in.close();
    }
}