题解 | 购物单

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 预算
        int m = in.nextInt(); // 物品总数

        // 存储每个物品的价格、重要度、主件编号
        int[][] items = new int[m + 1][3];
        // 存储每个主件的附件列表（主件编号从1开始）
        List<List<Integer>> attachments = new ArrayList<>();
        for (int i = 0; i <= m; i++) {
            attachments.add(new ArrayList<>());
        }

        for (int i = 1; i <= m; i++) {
            items[i][0] = in.nextInt(); // 价格v
            items[i][1] = in.nextInt(); // 重要度w
            items[i][2] = in.nextInt(); // 主件编号q
            if (items[i][2] != 0) {
                attachments.get(items[i][2]).add(i);
            }
        }

        // 整理分组：每个组是主件及其附件的所有可能组合
        List<List<int[]>> groups = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            if (items[i][2] == 0) { // 是主件
                List<int[]> group = new ArrayList<>();
                // 组合1：仅主件
                group.add(new int[]{items[i][0], items[i][0] * items[i][1]});
                List<Integer> atts = attachments.get(i);
                // 组合2：主件 + 附件1（如果有）
                if (atts.size() >= 1) {
                    int v = items[i][0] + items[atts.get(0)][0];
                    int s = items[i][0] * items[i][1] + items[atts.get(0)][0] * items[atts.get(0)][1];
                    group.add(new int[]{v, s});
                }
                // 组合3：主件 + 附件2（如果有）
                if (atts.size() >= 2) {
                    int v = items[i][0] + items[atts.get(1)][0];
                    int s = items[i][0] * items[i][1] + items[atts.get(1)][0] * items[atts.get(1)][1];
                    group.add(new int[]{v, s});
                }
                // 组合4：主件 + 附件1 + 附件2（如果有两个附件）
                if (atts.size() == 2) {
                    int v = items[i][0] + items[atts.get(0)][0] + items[atts.get(1)][0];
                    int s = items[i][0] * items[i][1] + items[atts.get(0)][0] * items[atts.get(0)][1] + items[atts.get(1)][0] * items[atts.get(1)][1];
                    group.add(new int[]{v, s});
                }
                groups.add(group);
            }
        }

        // 分组背包DP
        int[] dp = new int[n + 1];
        for (List<int[]> group : groups) {
            // 逆序遍历预算，避免重复选择
            for (int j = n; j >= 0; j--) {
                for (int[] comb : group) {
                    int cost = comb[0];
                    int score = comb[1];
                    if (j >= cost) {
                        dp[j] = Math.max(dp[j], dp[j - cost] + score);
                    }
                }
            }
        }

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

其实我也不会写，都是靠AI的。