题解 | #购物单#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 物品类
    private static class good {
        public int v;  // 物品价格
        public int p;  // 重要程度
        public int q;  // 是否是附件
        public good a1 = null;
        public good a2 = null;

        public good(int v, int p, int q) {
            this.v = v;
            this.p = p;
            this.q = q;
        }

        public void setAppendGoods(good a) {
            if (this.a1 == null)
                this.a1 = a;
            else
                this.a2 = a;
        }

        public boolean isFollowed() {
            if (this.a1 == null && this.a2 == null)
                return false;
            else
                return true;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();  // 钱数
        int n = in.nextInt();  // 购买物品数

        List<good> input_good = new ArrayList<>();  // 存储输入值
        List<good> input_follow_good = new ArrayList<>();
        Map<Integer, Integer> map = new
        HashMap<Integer, Integer>(); // 存储主件位置
        int totalCount = 0;  // 记录主件原始数组中位置
        int mainCount = 0;  // 记录主件在主件数组中位置
        while (in.hasNext()) {
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();

            if (q != 0)
                input_follow_good.add(new good(v, p, q));
            else {
                input_good.add(new good(v, p, q));
                map.put(totalCount, mainCount);
                mainCount++;
            }
            totalCount++;
        }

        int index = 0;
        // 插入辅件
        if (!input_follow_good.isEmpty()) {
            for (good g : input_follow_good) {
                index = map.get(g.q - 1);
                input_good.get(index).setAppendGoods(g);
            }
        }
        int len = input_good.size();

        int[][] dp = new int[m + 1][len + 1];
        // 边界条件 - dp[0][j] = 0 | dp[i][0] = 0
        // 辅件计算 - 0 选1 选2 两个都选
        // 状态转换方程 (不带辅件)dp[i][j] = Max(dp[i][j-1], dp[i-input[j][0]][j-1] + input[j][0] * input[j][1])  (携带辅件)dp[i][j] = Max(dp[i][j-1], dp[i-input[j][0]][j-1] + input[j][0] * input[j][1], dp[i-input[j][0]-input[j1][0]][j-1] + input[j][0] * input[j][1] +input[j1][0] * input[j1][1], ***)
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < len + 1; j++) {
                good temp = input_good.get(j - 1);
                dp[i][j] = dp[i][j - 1];
                if (i - temp.v >= 0) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - temp.v][j - 1] + temp.v * temp.p);
                    if (temp.isFollowed()) {
                        if (temp.a1 != null && i - temp.v - temp.a1.v >= 0) // 带附件1
                            dp[i][j] = Math.max(dp[i][j],
                                                dp[i - temp.v - temp.a1.v][j - 1] + temp.v * temp.p + temp.a1.v * temp.a1.p);
                        if (temp.a2 != null && i - temp.v - temp.a2.v >= 0) // 带附件2
                            dp[i][j] = Math.max(dp[i][j],
                                                dp[i - temp.v - temp.a2.v][j - 1] + temp.v * temp.p + temp.a2.v * temp.a2.p);
                        if (temp.a1 != null && temp.a2 != null &&
                                i - temp.v - temp.a1.v - temp.a2.v >= 0)  // 带附件1和2
                            dp[i][j] = Math.max(dp[i][j],
                                                dp[i - temp.v - temp.a1.v - temp.a2.v][j - 1] + temp.v * temp.p + temp.a1.v *
                                                temp.a1.p + temp.a2.v * temp.a2.p);
                    }
                }
            }
        }
        System.out.println(dp[m][len]);
    }
}