题解 | #购物单#

import java.util.Objects;
import java.util.Scanner;

/**
 * 购物车最大满意度
 * - 其实是0-1的背包问题，就是选择多一点动态规划
 * - 不要陷进附件影响主件的胡同里去
 * - 换个角度考虑，主件带动附件
 *
 * @date 2022/07/06
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();
        int itemNum = scanner.nextInt();
        Goods[] goodsArr = new Goods[itemNum];

        // 初始化
        for (int i = 0; i < itemNum; i++) {
            Goods goods = new Goods();
            goods.setPrice(scanner.nextInt());
            goods.setWeight(scanner.nextInt());
            int pindex = scanner.nextInt();
            goods.setPindex(pindex);
            goodsArr[i] = goods;
        }

        // 设置主附件关系
        for (int i = 0; i < goodsArr.length; i++) {
            Goods goods = goodsArr[i];
            if (goods.mainCheck()) {
                continue;
            }
            Integer pindex = goods.getPindex();
            Goods pg = goodsArr[pindex - 1];
            if (pg.getAttachOne() == null) {
                pg.setAttachOne(i);
            } else {
                pg.setAttachTwo(i);
            }
        }

        // 定义动态数组
        int[][] dp = new int[itemNum + 1][money + 1];

        // 明确base case,买0件满意度都会0，买0元钱都是0，默认

        // 两种状态的遍历
        for (int i = 1; i <= itemNum; i++) {
            for (int j = 1; j <= money; j++) {
                /**
                 * 明确选择，有五种
                 * - 啥都不买
                 * - 买主件
                 * - 买主件和附件1
                 * - 买主件和附件2
                 * - 买主件和附件1、2
                 */
                dp[i][j] = dp[i - 1][j];
                // 后面几种情况都是跟主件相关
                Goods goods = goodsArr[i - 1];
                if (!goods.mainCheck()) {
                    continue;
                }
                if (j >= goods.getPrice()) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.getPrice()] + goods.getGreatWight());
                }
                Integer attachOne = goods.getAttachOne();
                if (Objects.nonNull(attachOne) && attachOne >= 0) {
                    Goods goods1 = goodsArr[attachOne];
                    if (j >= (goods.getPrice() + goods1.getPrice())) {
                        dp[i][j] = Math.max(dp[i][j],
                                dp[i - 1][j - goods.getPrice() - goods1.getPrice()]
                                        + goods.getGreatWight() + goods1.getGreatWight());
                    }
                }

                Integer attachTwo = goods.getAttachTwo();
                if (Objects.nonNull(attachTwo) && attachTwo >= 0) {
                    Goods goods2 = goodsArr[attachTwo];
                    if (j >= (goods.getPrice() + goods2.getPrice())) {
                        dp[i][j] = Math.max(dp[i][j],
                                dp[i - 1][j - goods.getPrice() - goods2.getPrice()]
                                        + goods.getGreatWight() + goods2.getGreatWight());
                    }
                }

                attachOne = goods.getAttachOne();
                attachTwo = goods.getAttachTwo();
                if (Objects.nonNull(attachOne) && attachOne >= 0 && Objects.nonNull(attachTwo) && attachTwo >= 0) {
                    Goods goods1 = goodsArr[attachOne];
                    Goods goods2 = goodsArr[attachTwo];
                    if (j >= (goods.getPrice() + goods1.getPrice() + goods2.getPrice())) {
                        dp[i][j] = Math.max(dp[i][j],
                                dp[i - 1][j - goods.getPrice() - goods1.getPrice() - goods2.getPrice()]
                                        + goods.getGreatWight() + goods1.getGreatWight() + goods2.getGreatWight());
                    }
                }
            }
        }
        System.out.println(dp[itemNum][money]);
    }
    
    static class Goods {

        private int price;

        private int weight;

        private Integer pindex;

        private Integer attachOne;

        private Integer attachTwo;

        public boolean mainCheck() {
            return new Integer(0).equals(pindex);
        }

        public int getGreatWight() {
            return price * weight;
        }

        public Integer getPrice() {
            return price;
        }

        public void setPrice(Integer price) {
            this.price = price;
        }

        public Integer getWeight() {
            return weight;
        }

        public void setWeight(Integer weight) {
            this.weight = weight;
        }

        public Integer getPindex() {
            return pindex;
        }

        public void setPindex(Integer pindex) {
            this.pindex = pindex;
        }

        public Integer getAttachOne() {
            return attachOne;
        }

        public void setAttachOne(Integer attachOne) {
            this.attachOne = attachOne;
        }

        public Integer getAttachTwo() {
            return attachTwo;
        }

        public void setAttachTwo(Integer attachTwo) {
            this.attachTwo = attachTwo;
        }

        @Override
        public String toString() {
            return "Goods{" +
                    "price=" + price +
                    ", weight=" + weight +
                    ", pindex=" + pindex +
                    ", attachOne=" + attachOne +
                    ", attachTwo=" + attachTwo +
                    '}';
        }
    }
}