题解 | #购物单# 01背包扩展，可读性强解法

• 核心: dp[i] = max(dp[i], dp[i-主件], dp[i-主件-附件1], dp[i-主件-附件2], dp[i-主件-附件1-附件2])

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static class Item {
        int id;
        int mainId; // 附件才有
        int p;
        int v; // p * itemValue
        Item sub1;
        Item sub2;
    }

    // 每个主件可以有 0 个、 1 个或 2 个附件!!
    // items.size() < 60
    // limitMoney < 32000
    // dp[i] = max(dp[i], dp[i-主件], dp[i-主件-附件1], dp[i-主件-附件2], dp[i-主件-附件1-附件2])
    static int getMaxSatisfyValue(Map<Integer, Item> items, int limitMoney) {
        int[] dp = new int[limitMoney + 1];
        for (Item item : items.values()) {
            for (int i = limitMoney; i >= item.p;
                    i--) { // 尝试买当前物品, 倒着防重复
                dp[i] = Math.max(dp[i], dp[i - item.p] + item.v);
                if (item.sub1 != null) {
                    int idx = i - item.p - item.sub1.p;
                    if (idx >= 0) {
                        dp[i] = Math.max(dp[i], dp[idx] + item.v + item.sub1.v);
                    }
                }
                if (item.sub2 != null) {
                    int idx = i - item.p - item.sub2.p;
                    if (idx >= 0) {
                        dp[i] = Math.max(dp[i], dp[idx] + item.v + item.sub2.v);
                    }
                }
                if (item.sub1 != null && item.sub2 != null) {
                    int idx = i - item.p - item.sub1.p - item.sub2.p;
                    if (idx >= 0) {
                        dp[i] = Math.max(dp[i], dp[idx] + item.v + item.sub1.v + item.sub2.v);
                    }
                }
            }
        }
        return dp[limitMoney];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int limitMoney = in.nextInt();
        int itemCount = in.nextInt();
        List<Item> itemList = new ArrayList<>(itemCount);
        Map<Integer, Item> items = new HashMap<>();
        for (int id = 1; id <= itemCount; id++) {
            int p = in.nextInt();
            int value = in.nextInt();
            int mainId = in.nextInt();
            Item item = new Item();
            item.id = id;
            item.mainId = mainId;
            item.p = p;
            item.v = value * p;
            itemList.add(item);
            if (mainId == 0) {
                items.put(item.id, item);
            }
        }
        for (Item item : itemList) {
            if (item.mainId > 0) {
                Item mainItem = items.get(item.mainId);
                if (mainItem.sub1 == null) {
                    mainItem.sub1 = item;
                } else {
                    mainItem.sub2 = item;
                }
            }
        }
        int res = getMaxSatisfyValue(items, limitMoney);
        System.out.println(res);
    }
}