题解 | 购物单

import java.util.*;

/*
有依赖的背包问题
本质是选主件
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() / 10;  //预算
        int m = in.nextInt();  //物品总数

        int[] price = new int[m + 1]; //价格
        int[] value = new int[m + 1]; //v*w
        int[] point = new int[m + 1]; //从属主键，从1开始

        for (int i = 1; i <= m; i++) {
            price[i] = in.nextInt() / 10;
            value[i] = price[i] * in.nextInt();
            point[i] = in.nextInt();
        }

        //收集每个主件的附件列表 cp[0]、cp[1]都是一个ArrayList,表示第i个物品的附件列表
        List<Integer>[] cp = new ArrayList[m + 1];
        for (int i = 1; i <= m; i++) {
            cp[i] = new ArrayList<>();  //ArrayList初始化
        }
        for (int i = 1; i <= m; i++) {
            if (point[i] != 0) {  //也就是第i个物品有主件，主件在第 point[i]
                cp[point[i]].add(i);  //第 point[i]个物品增加附件"i"
            }
        }

        //分组背包 dp[1]：预算为10元时的当前最大满意度
        int[] dp = new int[n + 1];

        //遍历主件
        for (int i = 1; i <= m; i++) {
            if (point[i] != 0) continue;  //是附件,跳过

            //当前组内组合
            List<int[]> combos = new ArrayList<>();
            //组合一：只买主件
            combos.add(new int[] {price[i], value[i]});
            if (cp[i].size() >= 1) {  //有1个附件，增加组合二：主件+附件1
                int index = cp[i].get(0);  //该附件的顺序
                combos.add(new int[] {price[i] + price[index], value[i] + value[index]});
            }
            if (cp[i].size() ==
                    2) {  //有2个附件，增加组合三:主件+2*附件和组合四:主件+附件2
                int index1 = cp[i].get(0);
                int index2 = cp[i].get(1);
                combos.add(new int[] {price[i] + price[index2], value[i] + value[index2]});
                combos.add(new int[] {price[i] + price[index1] + price[index2], value[i] + value[index1] + value[index2]});
            }

            //分组背包，先复制旧 dp
            int[] old = dp.clone();
            for (int j = 1; j <= n; j++) {  //每个预算下的最大满意度
                for (int[] combo : combos) {
                    int totalPrice = combo[0];
                    int totalValue = combo[1];
                    if (j >= totalPrice) {  //预算超过价格，即买得起
                        dp[j] = Math.max(dp[j], old[j - totalPrice] + totalValue);
                    }
                }
            }
        }

        //找最大满意度
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.print(ans * 10);
    }
}