UVa 266 Stamping Out Stamps-平芜编程栈

题目分析

题目描述了一个邮票组合问题，具体要求如下：

邮局最多提供101010种不同面值的邮票。
每张包裹上最多只能贴101010枚邮票。
给定一个需要支付的邮资金额（单位为美分），要求用邮票组合出该金额，使得：
1. 如果能够恰好组成该金额，则选择邮票数量最少的方案；
2. 如果无法恰好组成，则选择超出金额最小的方案；
3. 如果仍有多种方案（相同数量、相同超出值），则选择邮票面值尽可能大的方案（即字典序最大，按降序排列邮票面值）。
输出时，对于每个测试数据集，先输出邮票面值（升序），然后对于每个查询金额，输出AMOUNT x和STAMPS USED后面跟所用的邮票面值（降序）。
如果无解（即无法用不超过 10 枚邮票组成金额或超出值），输出NO SOLUTION EXISTS。

解题思路

问题建模

这是一个典型的有限背包 / 完全背包 + 多目标优化问题。与普通背包不同，我们不仅要考虑能否组成目标金额，还要考虑：

最小化超出值；
在超出值相同时，最小化邮票数量；
在前两者相同时，最大化邮票面值的字典序（即降序排列尽可能大）。

由于每张包裹最多101010枚邮票，且面值最大不超过29.9929.9929.99美分（即299929992999美分），但题目中输入的面值可能较大（如167654316765431676543美分），不过由于最多101010枚邮票，实际组成的总额不会超过10×max⁡(values)10 \times \max(values)10×max(values)。因此我们可以将搜索空间限制在一个合理的上界内。

算法选择

常见的解法有：

BFS\texttt{BFS}BFS：以金额为状态，每次添加一枚邮票，记录使用的邮票数量和最后一步。
DP\texttt{DP}DP（动态规划）：定义dp[i]表示组成金额i所需的最少邮票数，并记录路径。

由于金额范围可能较大（例如输入中出现了167654316765431676543），但邮票数量限制为101010，因此实际可达的金额不会太大。我们可以设定一个搜索上界，例如max(values) * 10，因为如果目标金额超过这个值，显然无法用101010枚邮票覆盖（除非面值很大，但面值也是给定的，所以这个上界是安全的）。

动态规划状态设计

定义：

coverage[i]：组成金额i所需的最少邮票数量。初始化为一个很大的数（如100001000010000），表示不可达。
parent[i][0]：组成金额i时，前一个状态的金总额（即去掉最后一枚邮票后的金额）。
parent[i][1]：组成金额i时，最后一枚邮票的面值。

转移方程（完全背包，每个面值可用多次，但总邮票数不超过101010）：

如果 i≥values[j] 且 coverage[i−values[j]]+1<coverage[i] \text{如果 } i \geq values[j] \text{ 且 } coverage[i - values[j]] + 1 < coverage[i]如果i≥values[j]且coverage[i−values[j]]+1<coverage[i]

则更新coverage[i]并记录父节点。

超出金额的处理

如果coverage[amount] > 10，说明无法用不超过101010枚邮票恰好组成amount，则从amount + 1开始向上寻找第一个能用不超过101010枚邮票组成的金额，作为新的目标金额。

上界的确定

代码中数组大小固定为310031003100，这是基于面值最大约300300300美分、101010枚邮票最多300030003000美分左右的假设。如果面值很大（如输入中的167654316765431676543），则amount可能远大于310031003100，此时代码会直接判断amount > values.front() * 10（其中values.front()是最大面值）并输出NO SOLUTION EXISTS。这是合理的，因为101010枚最大面值邮票都达不到amount，必然无解。

回溯路径

从parent[amount][0]开始向前回溯，收集所有邮票面值，最后按降序输出。

代码实现

// Stamping Out Stamps// UVa ID: 266// Verdict: Accepted// Submission Date: 2016-06-09// UVa Run Time: 0.140s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>values;// 存储邮票面值intn;// 邮票种类数// 将给定金额转换为邮票组合voidconvert(intamount){// coverage[i] 表示组成金额 i 所需的最少邮票数// parent[i][0] 表示组成金额 i 的前一个金额// parent[i][1] 表示组成金额 i 时使用的最后一枚邮票面值intcoverage[3100],parent[3100][2];// 初始化for(inti=0;i<3100;i++){coverage[i]=10000;// 初始化为一个大数，表示不可达parent[i][0]=-1;parent[i][1]=-1;}coverage[0]=0;// 金额 0 不需要邮票// 完全背包 DP，金额从 1 到 3099for(inti=1;i<3100;i++)for(intj=0;j<n;j++){// 如果当前金额 i 可以减去一个邮票面值，且新方案邮票数更少if(i>=values[j]&&(coverage[i-values[j]]+1)<coverage[i]){coverage[i]=coverage[i-values[j]]+1;parent[i][0]=i-values[j];parent[i][1]=values[j];}}// 如果无法用不超过 10 枚邮票恰好组成 amount，则寻找超出 amount 的最小金额if(coverage[amount]>10){for(inti=amount+1;i<3100;i++)if(coverage[i]<=10){amount=i;break;}}// 回溯路径，收集使用的邮票vector<int>stamps;intend=parent[amount][0];stamps.push_back(parent[amount][1]);while(parent[end][0]!=-1){stamps.push_back(parent[end][1]);end=parent[end][0];}// 按降序输出邮票面值sort(stamps.begin(),stamps.end(),greater<int>());cout<<"STAMPS USED";for(inti=0;i<stamps.size();i++)cout<<" "<<stamps[i];cout<<endl;}intmain(intargc,char*argv[]){while(cin>>n,n>0){values.resize(n);for(inti=1;i<=n;i++)cin>>values[i-1];// 输出邮票面值（升序）sort(values.begin(),values.end());cout<<"STAMP VALUES";for(inti=0;i<values.size();i++)cout<<" "<<values[i];cout<<endl<<endl;// 将面值反转为降序，以便 DP 时优先考虑大面值reverse(values.begin(),values.end());intamount;while(cin>>amount,amount>0){cout<<"AMOUNT "<<amount<<endl;// 如果最大面值的 10 倍仍小于 amount，则无解if(amount>values.front()*10)cout<<"NO SOLUTION EXISTS"<<endl;elseconvert(amount);cout<<endl;}}return0;}