【题目来源】
https://www.luogu.com.cn/problem/P2725
https://www.acwing.com/problem/content/1382/
【题目描述】
给一组 n 枚邮票的面值集合和一个上限 k——表示信封上能够贴 k 张邮票。请求出最大的正整数 m，满足 1 到 m 的面值都可以用不超过 k 张邮票表示出来。
【输入格式】
输入的第一行是两个整数，分别代表邮票上限 k 和邮票面值数 n。
自第二行起，除最后一行外，每行有 15 个整数 ai，最后一行的整数个数不超过 15，共有 n 个整数，第 i 个整数代表第 i 种邮票的面值 ai。
【输出格式】
输出一行一个整数代表 m。若 m 不存在请输出 0。
【输入样例】
5 2
1 3
【输出样例】
13
【数据范围】
对于 100% 的数据，保证 1≤k≤200，1≤n≤50，1≤ai≤10^4。
【算法分析】
● 邮票拼凑问题，等价于一个“节点为邮资、边为加一张邮票、边权固定为 1”的无权有向图。
● 邮票拼凑问题的本质是：构造一个以邮资为节点、加一张邮票为边的无权图，通过 BFS 求起点 0 到所有节点的最短路径长度，再筛选出满足路径长度 ≤k 的连续节点序列，其最大值就是答案。
● 邮票拼凑问题的两个核心目标
目标 1：对每个邮资 x，求拼凑出 x 所需的最少邮票张数，记为 cnt[x]。
目标 2：找到从 1 开始的最大连续邮资：第一个无法用 ≤k 张邮票拼凑的 x，其前一个数就是答案。
● 邮票拼凑问题转化为图的最短路径目标
目标 1 转化为求从起点节点 0（邮资 0）到目标节点 x（邮资 x）的最短路径长度，这个长度就是 cnt[x]。起点节点 0 的意义：拼凑邮资 0 需要 0 张邮票，对应路径长度为 0。
目标 2 则是在最短路径的基础上做筛选。筛选出所有满足“最短路径长度 ≤k”的节点 x，找到从 1 开始的最大连续序列。
● 关键等价性证明：
路径长度 = 边数 = 邮票张数；
最短路径长度 = 最少边数 = 最少邮票张数；
【算法代码】
代码中的 N 要取到1e7，否则有的样例不过。
#include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=1e7; int cnt[N+1]; //cnt[x]=min-number of stamps to construct postage x int val[55]; //Store the face values of n types of vals int k,n; //num of stamps is k, face value of stamps is n int bfs() { queue<int> q; q.push(0); //To construct postage 0, you need 0 stamps cnt[0]=0; while(!q.empty()) { int t=q.front(); q.pop(); for(int i=0; i<n; i++) { int nxt=t+val[i]; if(nxt>=N) continue; //Exceeding postage upper limit if(cnt[nxt]>cnt[t]+1 && cnt[t]+1<=k) { cnt[nxt]=cnt[t]+1; q.push(nxt); } } } for(int i=1; i<N; i++) { if(cnt[i]>k) { return i-1; } } return N-1; } int main() { memset(cnt,inf,sizeof cnt); cin>>k>>n; for(int i=0; i<n; i++) { cin>>val[i]; } cout<<bfs()<<endl; return 0; } /* in: 200 14 1 2 4 15 9 31 63 2100 3500 127 255 511 1000 1999 out: 682938 */
【参考文献】
https://www.acwing.com/solution/content/31236/
https://www.cnblogs.com/sirr01uta/p/18880867
