题解 | 购物单

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    static class Products {
        int price;
        int important;
        int index;

        public Products(int price, int important, int index) {
            this.price = price;
            this.important = important;
            this.index = index;

        }

        //字符串方法
        public String toString() {
            return "价格：" + price + " 重要度：" + important + " 索引：" + index;
        }
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] split = s.split(" ");
        int amount = Integer.parseInt(split[0]);
        int productCount = Integer.parseInt(split[1]);

        ArrayList<Products> mainList = new ArrayList<>();
        ArrayList<ArrayList<Products>> attachList = new ArrayList<>();//动态数组中的元素也是动态数组；方便一个主件存入多个附件！
        for (int i = 0; i < productCount; i++) {
            attachList.add(new ArrayList<>());
        }
        int record = 0;
        for (int i = 0; i < productCount; i++) {
            String proStr = in.nextLine();
            String[] proSplit = proStr.split(" ");
            int price = Integer.parseInt(proSplit[0]);
            int important = Integer.parseInt(proSplit[1]);
            int mainProductIndex = Integer.parseInt(proSplit[2]);
            int index = record;

            if (mainProductIndex == 0) {
                //存主件
                Products products = new Products(price, important, index);
                mainList.add(products);
            } else {
                //存附件
                if (attachList.get(mainProductIndex - 1) == null) {
                    attachList.set(mainProductIndex - 1, new ArrayList<>());
                }
                Products products = new Products(price, important, index);
                attachList.get(mainProductIndex - 1).add(products);
                //在通过 get 拿到了具体的容器对象（比如是一个 List 类型的对象）之后，使用 add 方法就是为了向这个容器里面添加新的元素（在这里是 products，它可能是一个商品对象、数据记录等具体的实体元素）。
                //整体上先 get 找到要操作的目标容器对象，再利用该对象的 add 方法来向其内部添加需要的元素
            }
            record++;
        }

        int[] dp = new int[amount + 1];
        dp[0] = 0;

        for (int i = 0; i < mainList.size(); i++) {
            Products products = mainList.get(i);
            int price = products.price;
            int important = products.important;
            int index = products.index;

            for (int j = amount; j > 0; j--) {
                //如果为空只考虑加或不加主件
                if (attachList.get(index).isEmpty()) {
                    if (j >= price) {
                        dp[j] = Math.max(dp[j], dp[j - price] + important * price);
                    }
                } else {
                    //如果有附件 先看看存不存主件
                    if (j >= price) {
                        dp[j] = Math.max(dp[j], dp[j - price] + important * price);
                    }
                    //在分别考虑 主件+附件1 和 主件+附件2  要不要为dp[j构成满意度
                    for (int k = 0; k < attachList.get(index).size(); k++) {
                        Products attachProducts = attachList.get(index).get(k);//先再到存附件的容器，再拿到指定的附件
                        int attachPrice = attachProducts.price;
                        int attachImportant = attachProducts.important;

                        if (j >= price + attachPrice) {
                            dp[j] = Math.max(dp[j], dp[j - price - attachPrice] + important * price +
                                             attachImportant * attachPrice);
                        }
                    }
                    //如果有两个附件 还要考虑主件+两个附件 要不要为dp[j]构成满意度
                    if (attachList.get(index).size() > 1) {
                        Products attachProducts1 = attachList.get(index).get(0);
                        int attachPrice1 = attachProducts1.price;
                        int attachImportant1 = attachProducts1.important;
                        Products attachProducts2 = attachList.get(index).get(1);
                        int attachPrice2 = attachProducts2.price;
                        int attachImportant2 = attachProducts2.important;
                        int sumPrice = price + attachPrice1 + attachPrice2;
                        int sumImportant = important * price + attachImportant1 * attachPrice1 +
                                           attachImportant2 * attachPrice2;
                        if (j >= sumPrice) {
                            dp[j] = Math.max(dp[j], dp[j - sumPrice] + sumImportant);
                        }
                    }
                }
            }
        }
        System.out.println(dp[amount]);
    }
}