题解 | 最小邮票数

#include <cstring>
#include <iostream>
using namespace std;
const int M = 105, N = 25;
int m, n, p[N];

struct node {
    int cur, num, start; //当前剩余总值，已经选取的邮票数，下次开始遍历邮票的索引；
} q[M * M];

int bfs(int sum) {
  //初始化队列
    int hh = 0, tt = -1;
    q[++tt] = {sum, 0, 0};

    while (tt >= hh) {
        node t = q[hh++];
        for (int i = t.start; i < n; i++) {
            int new_cur = t.cur - p[i];
            if (new_cur > 0) {
                q[++tt] = {new_cur,t.num + 1,i+1};
            }
            if (new_cur == 0) {
                return t.num + 1;
            }
        }
    }
    return 0; //无解返回0；
}

int main() {
    while (cin >> m >> n) {
        //初始化，输入邮票
        for (int i = 0; i < n; i++) cin >> p[i];

        cout << bfs(m) << endl;
    }
}
// 64 位输出请用 printf("%lld")

【思路】：一看到要求最少邮票数，我就想到了宽搜BFS具有最短路的特性，果断使用了BFS，但是这道题有坑，需要记录每个节点已经使用过了那几张邮票，起初我在结构体中设置了一个数组，来记录每个节点能使用那张邮票，如下：

struct node {
    int cur, num;
    bool vis[N]; //记录每个节点可以使用的邮票
} q[M*M*M*M];

结果发现节点太多后，内存就超限了。。。。

然后问了AI，才知道这种情况下要优化代码，减去一些不必要的搜索；解释如下：

这里的关键是：

索引控制法的核心是 “避免重复的组合”，而不是单纯 “标记某一张邮票是否被使用”。它通过限制 “只能选择索引更大的邮票”，确保每个可能的组合只被考虑一次，从而间接实现了 “不重复使用邮票” 的效果，同时还能减少冗余计算。

为什么要 “去掉 start 以前所有的邮票”？

假设邮票索引为 0,1,2,...,n-1，且按升序排列。索引控制法要求 “每次只能从 start 及以后的邮票中选择”，本质是强制组合中的邮票索引必须是 “递增的”（例如 i < j < k）。

这样做的原因是：不同顺序的同一张邮票组合是等价的。

比如，有邮票 [3,3,4]（索引 0、1、2），凑 10 分的有效组合是 3（0）+3（1）+4（2）。如果不限制顺序，可能会出现：

• 先选 0，再选 1，再选 2
• 先选 1，再选 0，再选 2（重复组合，因为用的是同三张邮票）

这些组合本质上是同一个解（用了相同的邮票），但会被重复计算。而通过 start 控制，只能按 0→1→2 的顺序选择，自然排除了所有 “索引非递增” 的重复组合。

这样会不会漏掉有效组合？

不会。因为任何有效的邮票组合，都一定存在一个 “索引递增” 的选择顺序。

比如，假设存在一个有效组合用到了邮票 i, j, k（i < j < k），那么在搜索时：

• 第一次会从 start=0 中选择 i，新的 start 设为 i+1
• 第二次会从 start=i+1 中选择 j（j > i，符合条件），新的 start 设为 j+1
• 第三次会从 start=j+1 中选择 k（k > j，符合条件）

这个组合一定会被搜索到。

反之，如果一个组合的邮票索引不是递增的（比如 j, i 且 j > i），它本质上和 i, j 是同一个组合，没必要重复计算。

对比 “标记单张邮票” 和 “索引控制”

总结

索引控制法通过 “限制只能选择索引更大的邮票”，用最简洁的方式同时实现了两个目标：

1. 避免重复使用单张邮票（因为每个邮票只能在 “索引≥start” 时被选一次）；
2. 避免重复计算等价组合（因为组合顺序被固定为索引递增）。

这种方法看似 “去掉了 start 以前所有邮票”，但实际上并没有漏掉任何有效解，反而通过减少冗余状态，让算法更高效。

还有那些情景适合使用该办法优化：

索引控制法（通过限制选择范围的起始索引来避免重复组合）是一种针对组合问题的高效优化手段，尤其适合以下情景：

1. 求解 “无顺序要求的组合问题”

当问题的核心是 “选择元素的组合” 而非 “选择元素的顺序” 时，该方法能最大化减少冗余计算。

• 典型场景：邮票 / 硬币凑钱问题（如示例代码，只需选出若干邮票的总和等于目标值，与选择顺序无关）；子集和问题（从数组中选若干元素，和为目标值，子集内元素无顺序）；组合总和问题（如 “从候选数中选 k 个数，和为 target”，不考虑顺序）。
• 核心原因：这类问题中，[a,b] 和 [b,a] 是同一个组合，索引控制通过强制 “按索引递增选择”，直接排除所有顺序不同的重复组合，无需额外去重。

2. 需 “避免元素重复使用” 的场景

当问题要求 “每个元素只能使用一次” 时，索引控制法能自然实现这一约束，且比 “标记已用元素” 更高效。

3. 追求 “最小步骤 / 最短路径” 的搜索问题

当问题需要找到 “使用元素数量最少” 的解（如示例中 “最少邮票张数”），结合 BFS 使用索引控制法时，能在保证正确性的前提下，优先找到最优解。

4. 元素 “可重复但组合需去重” 的场景

即使问题允许元素重复使用（如 “邮票可以重复选”），稍作修改后，索引控制法仍可适用（此时下一次选择的start设为i而非i+1），避免如[a,a]和[a,a]（不同顺序导致的重复）。

不适合的场景

• 有顺序要求的问题（如排列问题，[a,b]和[b,a]是不同解）；
• 元素本身可重复且需要区分位置的问题（如数组[2,2]中两个2是不同位置，需视为不同元素）。

只要问题的解与元素选择顺序无关，且需避免重复组合，都可以考虑使用该方法。