考点：穷举

数据规模 n ≤ 20 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 20
• 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
• 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：穷举

本题切入点

n≤20，商品选/不选共 2²⁰ 种组合，直接枚举子集：算原价、按所选是否含 ≥3 个不同类别选满减规则（每满 200 减 20 或减 30），在折后价 ≤ 预算中取最大满意度。

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

1. 确定枚举什么（下标区间 / 子集 / 数值）。
2. 用一层或多层循环（或递归）生成所有候选。
3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

• 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
• 去重没做好，同一种方案被多次统计。

对照本题

• 数据规模 n ≤ 20，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。

样例解读

样例 1：输入 100 / 3 / 10001 1 100 90 / 10002 2 100 100 / 10003 3 100 110 → 输出 110

预算只能购买其中一件。

样例 2：输入 200 / 4 / 10001 1 200 200 / 10002 2 10 10 / 10003 3 10 10 / 10004 3 10 10 → 输出 230

四件原价 230，三个类别触发减 30，折后正好 200。