题解 | #购物单#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String Nm = scan.nextLine().trim();
        int N = Integer.valueOf(Nm.split(" ")[0]); // N -> 总钱数
        int m = Integer.valueOf(Nm.split(" ")[1]); // m -> 可购买的物品的个数
        int[] prices = new int[m + 1]; // 定义一个整型数组，用于存放每一个物品的价格
        int[] importance = new int[m + 1]; // 定义一个整型数组，用于存放每一个物品的重要程度
        int[] devices = new int[m + 1]; // 定义一个整型数组，用于存放每一个物品到底是主件还是附件
        int masterDevices = 0; // 定义一个整型变量，用于存放主件的个数
        HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>(); // 定义一个 HashMap，用于存放每一个主件，它的附件有哪些
        HashMap<Integer, ArrayList<ArrayList<Integer>>> masterGoods = new HashMap<>(); // 定义一个 HashMap，用于存放每一个主件，它的购买组合有哪一些
        for (int i = 1; i <= m; i++) { // 获取 m 个物品的信息
            String tmp = scan.nextLine();
            String[] strs = tmp.split(" ");
            prices[i] = Integer.valueOf(strs[0]); // 获取该物品的价格
            importance[i] = Integer.valueOf(strs[1]); // 获取该物品的重要程度
            devices[i] = Integer.valueOf(strs[2]); // 获取该物品到底是主件还是附件
            if (devices[i] != 0) { // 如果当前物品是附件
                ArrayList<Integer> tmpArr = new ArrayList<>();
                ArrayList<Integer> masterArr = hashMap.getOrDefault(devices[i], tmpArr);
                masterArr.add(i); // 将当前附件添加到其主件所拥有的附件列表中去
                hashMap.put(devices[i], masterArr);
            } else { // 如果当前物品是主件
                masterDevices++;
            }
        }
        for (int i = 1; i <= m; i++) {
            if (devices[i] == 0) { // 如果当前物品是主件
                ArrayList<ArrayList<Integer>> tmpArr = new ArrayList<>();
                ArrayList<ArrayList<Integer>> currentMasterGoods = masterGoods.getOrDefault(i, tmpArr);
                ArrayList<Integer> currentGoodsInfo = new ArrayList<>(); // 定义一个一维数组，用于存放当前 组合 的信息
                currentGoodsInfo.add(prices[i]); // 单个物品的价格
                currentGoodsInfo.add(importance[i] * prices[i]); // 单个物品所能带来的满足感
                currentMasterGoods.add(currentGoodsInfo); // 将当前组合添加到集合当中去
                ArrayList<Integer> tmp = new ArrayList<>();
                ArrayList<Integer> masterArr = hashMap.getOrDefault(i, tmp); // 获取当前主件所拥有的附件列表
                if (masterArr.size() == 1) { // 如果只有一个附件
                    currentGoodsInfo = new ArrayList<>();
                    currentGoodsInfo.add(prices[i] + prices[masterArr.get(0)]);
                    currentGoodsInfo.add(importance[i] * prices[i] + importance[masterArr.get(0)] * prices[masterArr.get(0)]);
                    currentMasterGoods.add(currentGoodsInfo);
                } else if (masterArr.size() == 2) { // 如果有两个附件
                    currentGoodsInfo = new ArrayList<>();
                    currentGoodsInfo.add(prices[i] + prices[masterArr.get(0)]);
                    currentGoodsInfo.add(importance[i] * prices[i] + importance[masterArr.get(0)] * prices[masterArr.get(0)]);
                    currentMasterGoods.add(currentGoodsInfo);
                    currentGoodsInfo = new ArrayList<>();
                    currentGoodsInfo.add(prices[i] + prices[masterArr.get(1)]);
                    currentGoodsInfo.add(importance[i] * prices[i] + importance[masterArr.get(1)] * prices[masterArr.get(1)]);
                    currentMasterGoods.add(currentGoodsInfo);
                    currentGoodsInfo = new ArrayList<>();
                    currentGoodsInfo.add(prices[i] + prices[masterArr.get(0)] + prices[masterArr.get(1)]);
                    currentGoodsInfo.add(importance[i] * prices[i] + importance[masterArr.get(0)] * prices[masterArr.get(0)] + importance[masterArr.get(1)] * prices[masterArr.get(1)]);
                    currentMasterGoods.add(currentGoodsInfo);
                }
                masterGoods.put(i, currentMasterGoods);
            }
        }
        int[][] dp = new int[masterDevices + 1][N + 1]; // 定义一个二维数组    dp[i][j] -> 当物品数为 i、金钱数为 j 时，所能获得的最大的满足度
        int index = 1;
        for (int Goods = 1; Goods <= m; Goods++) { // 当前的物品
            if (devices[Goods] != 0) { // 如果当前物品不是主件，直接跳过当次循环
                continue;
            }
            for (int Money = 0; Money <= N; Money++) { // 当前的金钱
                dp[index][Money] = dp[index - 1][Money]; // 对于当前的主件，我们可以选择不买
                ArrayList<ArrayList<Integer>> currentMasterGoods = masterGoods.get(Goods);
                for (ArrayList<Integer> tmpArr : currentMasterGoods) { // 获取每一种组合
                    if (tmpArr.get(0) <= Money) {
                        dp[index][Money] = Math.max(dp[index][Money], tmpArr.get(1) + dp[index - 1][Money - tmpArr.get(0)]);
                    }
                }
            }
            index++;
        }
        System.out.println(dp[masterDevices][N]); // 输出最终的结果
    }
}