题解 | #购物单#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();  // 总钱数
        int N = scanner.nextInt();  // 可购买的物品个数
        Good[] goods = new Good[N + 1];

        for (int i = 1; i <= N; i++) {
            int v = scanner.nextInt();
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            goods[i] = new Good(v, p, q);
        }
        for (int i = 1; i <= N; i++) {
            if (goods[i].q > 0) {
                if (goods[goods[i].q].a1 == 0) {
                    goods[goods[i].q].setA1(i);
                } else {
                    goods[goods[i].q].setA2(i);
                }
            }
        }


        int[][] dp = new int[N + 1][money + 1];  // 动态规划数组

        for (int i = 1; i <= N; i++) {
            int v = goods[i].v;
            for (int j = 1; j <= money; j++) {
                if (goods[i].q > 0) {// 附件
                    dp[i][j] = dp[i - 1][j];
                } else { // 主件
                    dp[i][j] = dp[i - 1][j];
                    //只有主件
                    if (v <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods[i].v] + goods[i].v * goods[i].p);
                    }
                    // 附件必须购买其对应的主件,只有一个附件a2或者只有一个附件a1
                    if (goods[i].a2 != 0 && v + goods[goods[i].a2].v <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v - goods[goods[i].a2].v] + goods[i].v * goods[i].p + goods[goods[i].a2].v * goods[goods[i].a2].p);
                    }
                    if (goods[i].a1 != 0 && v + goods[goods[i].a1].v <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v - goods[goods[i].a1].v] + goods[i].v * goods[i].p + goods[goods[i].a1].v * goods[goods[i].a1].p);
                    }
                    //  附件必须购买其对应的主件, 同时有两个附件a1、a2
                    if (goods[i].a1 != 0 && goods[i].a2 != 0 && v + goods[goods[i].a1].v + goods[goods[i].a2].v <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v - goods[goods[i].a1].v - goods[goods[i].a2].v] + goods[i].v * goods[i].p
                                + goods[goods[i].a1].v * goods[goods[i].a1].p + goods[goods[i].a2].v * goods[goods[i].a2].p);
                    }
                }
            }
        }
        System.out.println(dp[N][money]);
    }

    static class Good {
        public int v;//价格
        public int p;//重要度
        public int q;//主件or附件
        public int a1 = 0;//附件1ID
        public int a2 = 0;//附件2ID

        public Good() {
        }

        public Good(int v, int p, int q, int a1, int a2) {
            this.v = v;
            this.p = p;
            this.q = q;
            this.a1 = a1;
            this.a2 = a2;
        }

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

        /**
         * 获取
         *
         * @return v
         */
        public int getV() {
            return v;
        }

        /**
         * 设置
         *
         * @param v
         */
        public void setV(int v) {
            this.v = v;
        }

        /**
         * 获取
         *
         * @return p
         */
        public int getP() {
            return p;
        }

        /**
         * 设置
         *
         * @param p
         */
        public void setP(int p) {
            this.p = p;
        }

        /**
         * 获取
         *
         * @return q
         */
        public int getQ() {
            return q;
        }

        /**
         * 设置
         *
         * @param q
         */
        public void setQ(int q) {
            this.q = q;
        }

        /**
         * 获取
         *
         * @return a1
         */
        public int getA1() {
            return a1;
        }

        /**
         * 设置
         *
         * @param a1
         */
        public void setA1(int a1) {
            this.a1 = a1;
        }

        /**
         * 获取
         *
         * @return a2
         */
        public int getA2() {
            return a2;
        }

        /**
         * 设置
         *
         * @param a2
         */
        public void setA2(int a2) {
            this.a2 = a2;
        }

        public String toString() {
            return "Good{v = " + v + ", p = " + p + ", q = " + q + ", a1 = " + a1 + ", a2 = " + a2 + "}";
        }

    }
}