题解 | #购物单#

import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class Good {
        int[] prices;
        int[] values;

        public Good() {
            prices = new int[] {0, 0, 0, 0};
            values = new int[] {0, 0, 0, 0};
        }

        @Override
        public String toString() {
            return "MainEntry{" +
                   "prices=" + prices +
                   ", values=" + values +
                   '}';
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 考虑背包问题，背还是不背，背包容量为n（钱数，可以理解为购买力，记为dp[][n]），物品重量即为v，贪心算法使得p*v累加最大满意度

        // 选择i商品，先判断是否是主件，是的话 需要根据情况决定背不背，否的话，需要先根据主件儿是否已经背上，如果没背上则不选，背上了则视情况背上该主件儿。
        // 还需要判断当前物品是否为配件，将主配件结合起来看，由于题目说明每个主件可以有 0 个、 1 个或 2 个附件，那么分为4种情况：
        // 1️⃣主件 2️⃣主件 + 配件1 3️⃣主件 + 配件2 4️⃣主件 + 配件1 + 配件2
        // 那么可以记录下所有主配件的关系，形成一个以主件编号为索引的列表
        // goods[i].prices[k]表示i主件商品分别选择0、1、2个配件的不同花费情况；goods[i].values[k]则表示i主件商品下分别选择0、1、2个配件产生的满意度。

        // n表示总钱数
        Integer n = in.nextInt();
        // m个可购买商品数
        Integer m = in.nextInt();

        TreeMap<Integer, Good> goodMap = new TreeMap<>();
        // i为物品编号，以输入物品顺序进行编号，当i为主件时，该主件的编号就是i
        for (int i = 0; i < m; i++) {
            int price = in.nextInt(); // 物品价格v
            int importance = in.nextInt(); // 物品的重要度p
            int belong = in.nextInt(); // 物品是主件还是附件q, 0是主件，大于0是附件，值代表所属主件的编号
            if (belong == 0) { // 添加主件
                Good good = goodMap.computeIfAbsent(i, k -> new Good());// 添加主件i
                good.prices[0] = price; // 记录价格
                good.values[0] = importance;// 记录重要度
            } else {
                Good good = goodMap.computeIfAbsent(belong - 1, k -> new Good());
                // 查看主件belong的附件情况，最多有2个附件
                if (good.prices[1] == 0) {
                    good.prices[1] = price;
                    good.values[1] = importance;
                } else if (good.prices[2] == 0) {
                    good.prices[2] = price;
                    good.values[2] = importance;
                }
            }
        }
        // 得到以物品主件为索引排序的，价格以及对应的重要度的主件商品列表
        Good[] goods = goodMap.values().toArray(new Good[0]);
        // 我们在这里预先把k种情况选择下不同的花费price总和以及产生的满意度总和预先计算出来
        for (int i = 0; i < goods.length; i++) {
            Good good = goods[i];
            // 更新values为k种情况的满意度price * importance
            good.values[0] = good.prices[0] * good.values[0];
            good.values[3] = good.values[0] + good.prices[1] * good.values[1] +
                             good.prices[2] * good.values[2];
            good.values[2] = good.values[0] + good.prices[2] * good.values[2];
            good.values[1] = good.values[0] + good.prices[1] * good.values[1];
            // 更新prices为k种情况的价格总和
            good.prices[3] = good.prices[0] + good.prices[1] + good.prices[2];
            good.prices[2] = good.prices[0] + good.prices[2];
            good.prices[1] = good.prices[0] + good.prices[1];
        }

        // dp[i][j]表示第i个主件物品及其附件背上放进容量为j的背包，满意度总和最大是多少
        // dp[i][j]的取值分为三种：
        // 1. 当前i主件物品不取：那么背包中最大满意度为dp[i-1][j]；
        // 2. 当前i主件物品取：那么当前选择的价格为goods[i].prices[k]，j-goods[i].prices[k] 则表示剩余购买力remainJ；那么背包的最大满意度为dp[i-1][j - remainJ] + goods[i].values[k]，其中 0 <= k <= 3，goods[i].prices[k]、goods[i].values[k]分别表示主件i取的情况下分别取0、1、2个附件的不同的花费总和以及满意度总和的情况
        // 所以这里需要一些整合，将goods[i].values[k]记为主件i的k种（0 <= k <= 3）满意度情况：∑(vi * pk)，goods[i].values[k]就表示主件物品i的附件k种选择的情况
        int[][] dp = new int[goods.length][n + 1];
        // 初始化，背包容量为0则任何物品都买不起（最大满意度都是0）
        for (int i = 0; i < goods.length; i++) {
            dp[i][0] = 0;
        }
        // 初始化，背包为j时，取第一个主件物品的最大满意度
        // 只有背包容量（购买力）大于等于价格时才进行初始化
        for (int j = goods[0].prices[0]; j <= n; j++) {
            int maxVal = goods[0].values[0]; // 这里最小的满意度是选择i=0的主件不含任何附件
            for (int k = 1; k < 4; k++) {
                if (j - goods[0].prices[k] >= 0) { // 要满足 选择主件+附件的总价格 <= j(购买力)
                    maxVal = Math.max(maxVal, goods[0].values[k]); // 取选择主件+附件的4种情况下的最大满意度
                }
            }
            dp[0][j] = maxVal;
        }
        // 以主件i为索引进行遍历每个主件+附件的选取情况
        for (int i = 1; i < goods.length; i++) {
            // 以购买力j为索引进行遍历在购买力为j的情况下够买i主件+附件的情况
            for (int j = 1; j <= n; j++) {
                int maxVal = dp[i - 1][j]; // 不取i主件时的满意度
                // 选取i主件时，要从k中情况中选取最大值（但要满足购买力）
                for (int k = 0; k < 4; k++) {
                    int remainJ = j -  goods[i].prices[k]; // 选取当前主件i时，不同的情况goods[i].prices[k]的价格要小于等于购买力j，这里记录剩余购买力remainJ需要大于等于0
                    if (remainJ >= 0) {
                        maxVal = Math.max(maxVal, dp[i - 1][remainJ] + goods[i].values[k]);
                    }
                }
                dp[i][j] = maxVal;
            }
        }
        System.out.println(dp[goods.length - 1][n]);
    }
}