HJ16. 购物单

题目描述

在预算 N 元内购买商品，每件商品有价格 v、重要度 p，可买可不买。部分商品是"主件"，部分是"附件"（每个主件最多有 2 个附件）。要购买附件必须先购买其主件。

目标：使"价格 × 重要度"的总和最大。

输入格式

• 第 1 行：预算 N、商品总数 m
• 第 m 行：每行 v p q，其中 q=0 表示该商品是主件，否则表示其所属主件编号

输出格式

一个整数，表示不超过预算时"价格 × 重要度"总和的最大值。

示例

示例 1

输入：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出：

2200

说明： 选择主件 1（800×2=1600）+ 附件 1（400×5=2000，共 1200 元）= 3600？不，注意预算只有 1000 元，无法同时购买 800+400。正确选择是主件 4（400×3=1200）+ 主件 5（500×2=1000）= 2200，总价 900 元。

---

解题思路

第一步：理解问题本质

这不是普通 0/1 背包，因为商品之间存在依赖关系：买了附件必须买主件。把"主件 + 它的附件"看成一个整体，每个整体有几种互斥的购买方案，本质是分组背包。

第二步：暴力解法（枚举组合）

枚举所有商品子集，检查是否满足预算和依赖关系，计算总价值取最大。

问题：商品数可达几十个，子集数为 2^m，指数级爆炸，无法接受。

第三步：转化为分组背包

每个主件连同附件构成一个"组"。组内只有 4 种互斥方案（最多 2 个附件）：

1. 只买主件
2. 主件 + 附件 1
3. 主件 + 附件 2
4. 主件 + 附件 1 + 附件 2

每个组只能选一种方案（或都不选）。分组背包 DP 即可解决。

第四步：最优解法（分组背包 DP）

状态：dp[j] 表示花费不超过 j 元时能获得的最大价值。

对每组做 0/1 背包，容量逆序遍历保证每组最多选一个组合：

for combos in groups:              # 遍历每组
    for j in range(money, -1, -1): # 逆序遍历容量
        for w, value in combos:    # 组内所有组合
            dp[j] = max(dp[j], dp[j - w] + value)

优化：价格与预算均为 10 的倍数，先全部除以 10，DP 数组缩小 10 倍，大幅提速。

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码1500 帧 · 录制输入

import sys


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    money = int(next(it)) // 10  # 预算除以 10
    m = int(next(it))

    items = [None] * (m + 1)          # items[i] = (价格/10, 价值)
    main_idx = []                      # 主件编号
    attachments = {}                  # 主件 -> 附件列表

    for i in range(1, m + 1):
        v, p, q = int(next(it)), int(next(it)), int(next(it))
        items[i] = (v // 10, v * p)
        if q == 0:
            main_idx.append(i)
            attachments[i] = []
        else:
            attachments.setdefault(q, []).append(i)

    groups = []
    for mi in main_idx:
        v0, val0 = items[mi]
        atts = attachments[mi]
        combos = [(v0, val0)]  # 只买主件
        for mask in range(1, 1 << len(atts)):  # 附件子集
            w, value = v0, val0
            for k, ai in enumerate(atts):
                if mask >> k & 1:
                    w += items[ai][0]
                    value += items[ai][1]
            combos.append((w, value))
        groups.append(combos)

    dp = [0] * (money + 1)
    for combos in groups:
        for j in range(money, -1, -1):
            for w, value in combos:
                if j >= w:
                    dp[j] = max(dp[j], dp[j - w] + value)

    print(dp[money])


if __name__ == "__main__":
    solve()

---

示例推演

以示例 1 为例，预算 1000 元，5 件商品：

编号	价格	重要度	q	价值
1	800	2	0	1600
2	400	5	1	2000
3	300	5	1	1500
4	400	3	0	1200
5	500	2	0	1000

分组：

• 组1（主件1 + 附件2、3）：{主件: 800/1600}、{主件+附件2: 1200/3600}、{主件+附件3: 1100/3100}、{主件+2+3: 1500/5100}
• 组2（主件4）：{400/1200}
• 组3（主件5）：{500/1000}

DP 过程（预算/10=100）：

• 组1 组合都超预算（最小 80 > 100 吗？不，80 ≤ 100），选 {800/1600}
• 组2：{400/1200}，组合花费 120 ≤ 100，可一起买 → 800+400=1200 ≤ 1000
• 组3：{500/1000}，再买 400+500=900 ≤ 1000 → 价值 1200+1000=2200

结果：2200。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举	O(2^m)	O(1)	指数级，不可行
分组背包	O(m·N)	O(N)	N 为预算，经 /10 优化后更快

m 为商品数，N 为预算

---

易错点总结

1. 忘记依赖关系

必须买主件才能买附件，直接把所有商品当普通 0/1 背包会选到孤立附件，错误。

2. 每组未逆序 DP

分组背包内必须逆序遍历容量，否则同一组多个组合可能被重复选用。

3. 价格未除以 10 导致超时

预算可达 30000+，不除以 10 时 DP 数组过大，先除以 10 可显著优化。

4. 附件先于主件出现

输入顺序不保证附件一定排在主件之后。若先登记了 attachments[主件]，后面遇到该主件时用 attachments[i] = [] 会覆盖清空已登记的附件。应改用 setdefault 或先判断是否已存在，避免丢失附件。

---

扩展思考

• 若附件数量不固定且更多，可对组内用「01 背包」思想枚举子集（用位运算）。
• 依赖关系可以推广到多级依赖（附件下还有附件），此时需用树形 DP / 有依赖背包。

---

相关题目

• HJ68. 成绩排序