题解 | #购物单#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //dp[j]花j元买物品所能达到的最大满意度
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();

        Good[] goods = new Good[m];
        for (int i = 0; i < m; i++) {
            goods[i] = new Good();
        }

        for (int i = 0; i < m; i++) {
            int v = scan.nextInt();
            int p = scan.nextInt();
            int isMain = scan.nextInt();
            //设置属性
            goods[i].v = v;
            goods[i].p = v * p;
            if (isMain == 0) {
                goods[i].isMain = true;
            } else if (goods[isMain - 1].a1 == -1) {
                goods[isMain - 1].a1 = i;
            } else {
                goods[isMain - 1].a2 = i;
            }
        }

        int[] dp = new int[n + 1];
        //dp[j]花j元买物品所能达到的最大满意度
        //dp[0] = 0;
        //01背包 先遍历物品再遍历背包 背包逆序
        for (int i = 0; i < m; i++) {
            for (int j = n; j >= 0; j--) {
                //5种情况
                //是附件，则不买该物品
                if (!goods[i].isMain) {
                    continue;
                }
                //是主件，买该物品
                if ( j >= goods[i].v) {
                    dp[j] = Math.max(dp[j], dp[j - goods[i].v] + goods[i].p);
                }
                //是主件，买该物品以及附件1
                if ( goods[i].a1 != - 1 && j >= goods[i].v + goods[goods[i].a1].v) {
                    dp[j] = Math.max(dp[j], dp[j - goods[i].v - goods[goods[i].a1].v] + goods[i].p + goods[goods[i].a1].p);
                }

                //是主件，买该物品以及附件2
                if (goods[i].a2 != - 1 &&
                        j >= goods[i].v + goods[goods[i].a2].v) {
                    dp[j] = Math.max(dp[j], dp[j - goods[i].v - goods[goods[i].a2].v] + goods[i].p + goods[goods[i].a2].p);
                }
                //是主件，买该物品已经两个附件
                if (goods[i].a1 != - 1 && goods[i].a2 != - 1 && j >= goods[i].v + goods[goods[i].a1].v + goods[goods[i].a2].v) {
                    dp[j] = Math.max(dp[j], dp[j - goods[i].v - goods[goods[i].a1].v - goods[goods[i].a2].v] + goods[i].p + goods[goods[i].a1].p + goods[goods[i].a2].p);
                }

            }
        }

        System.out.print(dp[n]);



    }

}
class Good {
    int v;//价格
    int p;//重要度&满意度
    boolean isMain;
    int a1 = -1;//附件1对应索引
    int a2 = -1;//附件2对应索引
}