题解 | #购物单#

购物单 参考了大神的代码，添加了一些注释

import java.util.*;


public class Main {
    public static void main(String[] argus) {
        Scanner scanner = new Scanner(System.in);
        int allMoney = scanner.nextInt();
        allMoney /= 10;
        int lineNum = scanner.nextInt();
        List<Product> list = new ArrayList<>();
        int num = 1;
        for (int i = 1; i <= lineNum; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            Product product = new Product(a / 10, b, c);
            product.num = num;
            list.add(product);
            num++;
        }
        for (int i = 0; i < list.size(); i++) {
            Product product = list.get(i);
            if (product.main != 0) {
                Product mainProduct = list.get(product.main - 1);
                if (mainProduct.fu1 == 0) {
                    mainProduct.fu1 = product.num;
                } else {
                    mainProduct.fu2 = product.num;
                }
            }
        }
        int[][] dp = new int[list.size() + 1][allMoney + 1];
        //先遍历物品，再遍历金额，附件会在主件时处理
        for (int i = 1; i <= list.size(); i++) {
            for (int j = 1; j <= allMoney; j++) {
                //1.主件
                Product a = list.get(i - 1);
                //选购这件主件物品所能带来的满意度增加值：
                int g1 = 0, g2 = 0, g3 = 0,
                    g4 = 0; //g1:仅主件，g2:主件+附件1，g3:主件+附件2，g4:主件+附件4
                int p1 = 0, p2 = 0, p3 = 0; //p1:主件价格，p2:附件1价格，p3:附件2价格
                p1 = a.price;
                if (a.main == 0) {
                    g1 = a.price * a.importent;
                    if (a.fu1 > 0) {
                        //有附件1
                        Product c = list.get(a.fu1 - 1);
                        p2 = c.price;
                        g2 = g1 + c.price * c.importent;
                    }
                    if (a.fu2 > 0) {
                        //有附件2
                        Product e = list.get(a.fu2 - 1);
                        p3 = e.price;
                        g3 = g1 + e.price * e.importent;
                    }
                    if (a.fu1 > 0 && a.fu2 > 0) {
                        g4 = g2 + g3 - g1;
                    }
                }
                //i是遍历的物品，j是遍历的金额
                //dp[i - 1][j - p1] + g1:意思是把p1的钱退出来的最优解+购买这件主件得到值g1
                //就是说拿这些钱购买这件物品会怎么样。
                dp[i][j] = j - p1 >= 0 ? Math.max(dp[i - 1][j],
                                                  dp[i - 1][j - p1] + g1) : dp[i - 1][j];
                //dp[i][j] 是上一步的最优解
                //dp[i - 1][j - p1 - p2]:把更多的钱退出来买主件+附件1
                dp[i][j] = j - p1 - p2 >= 0 ? Math.max(dp[i][j],
                                                       dp[i - 1][j - p1 - p2] + g2) : dp[i][j];

                dp[i][j] = j - p1 - p3 >= 0 ? Math.max(dp[i][j],
                                                       dp[i - 1][j - p1 - p3] + g3) : dp[i][j];

                dp[i][j] = j - p1 - p2 - p3 >= 0 ? Math.max(dp[i][j],
                           dp[i - 1][j - p1 - p2 - p3] + g4) : dp[i][j];
            }
        }
        System.out.println(dp[list.size()][allMoney] * 10);
    }

    public static class Product {
        public int num;
        public int price;
        public int importent;
        public int main;
        public int fu1;
        public int fu2;

        public Product(int price, int importent, int main) {
            this.price = price;
            this.importent = importent;
            this.main = main;
        }
    }
}