题目描述Ruritanian\texttt{Ruritanian}Ruritanian邮政服务RPS\texttt{RPS}RPS需要设计一种软件根据顾客需求和现有邮票面值为顾客分配邮票。每次分配最多使用444张邮票且要求总面值恰好等于顾客需求。在满足此条件的组合中优先选择不同面值类型最多的组合若类型数相同则选择总邮票张数最少的组合若仍相同则选择单张面值最高的组合即组合中最大面值最大若仍然无法区分则输出tie。若不存在任何组合则输出none。输入格式输入包含多组数据。每组数据由两行整数序列组成交替出现直到文件结束。第一行为可用邮票的面值序列以正整数给出以0结束。第二行为顾客需求序列以正整数给出以0结束。序列中的每个整数均用空格分隔可能跨行。输出格式对于每个顾客需求输出一行若存在合法组合输出需求值、括号内的类型数、冒号然后按非递减顺序列出所选邮票面值若唯一若存在多个并列最优则输出tie。若无合法组合输出需求值后跟---- none。具体格式见样例。样例输入1 2 3 0 7 4 0 1 1 0 2 3 0输出7 (3): 1 1 2 3 4 (2): 1 3 2 (2): 1 1 3 (2): tie题目分析本题本质上是带约束的组合搜索问题。邮票数量nnn不超过252525因为最多不同面值类型数为252525且每次最多使用444张邮票因此可以使用深度优先搜索DFS\texttt{DFS}DFS枚举所有可能的组合可重复选取但相同面值的邮票视为不同个体但由于只关心面值和类型数等价于允许重复使用同一种面值。对每个组合计算其面值总和、使用的张数、不同面值类型数以及最大面值按照题目定义的优先级比较记录最优组合。由于nnn较小枚举所有组合的数量级为O(n4)O(n^4)O(n4)完全可接受。解题思路读取邮票面值序列存入数组stamps[0..n-1]n为邮票个数包括重复面值。对于每个顾客需求request使用DFS\texttt{DFS}DFS搜索所有可能的组合参数当前深度depth已选邮票数起始索引idx允许选择从idx开始的邮票且允许重复选同一张因此递归时idx不变当前面值和sum。剪枝若depth 4或sum request则返回。若sum request则得到一个合法组合计算类型数通过setint存储不同面值、总张数depth1、最高面值并与当前最优比较若更优则更新最优组合。比较规则先比较类型数更大者优。若类型数相同比较总张数更小者优。若总张数相同比较最高面值更大者优。若三者均相同则视为并列最优保留多个组合用best向量存储所有并列最优组合。若best为空输出none若best大小为111输出唯一组合否则输出tie。注意输出时组合中的面值按非递减顺序输出。复杂度分析搜索深度最大444每次选择有nnn种可能最坏枚举n4n^4n4个组合n≤25n \le 25n≤25约390625390625390625完全可行。空间复杂度O(4)O(4)O(4)用于存储当前组合。代码实现// Stamps// UVa ID: 648// Verdict: Accepted// Submission Date: 2018-12-28// UVa Run Time: 0.020s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorvectorintbest;inttypes,total,highest,n,request;intstamps[32],used[4];voiddfs(intdepth,intidx,intsum){if(depth4||sumrequest)return;if(sumrequest){boolbetterfalse;setintdiff;for(inti0;idepth;i)diff.insert(used[i]);if(diff.size()types){best.clear();bettertrue;}elseif(diff.size()types){if(depth1total){best.clear();bettertrue;}elseif(depth1total){inth0;for(inti0;idepth;i)hmax(h,stamps[used[i]]);if(hhighest){best.clear();bettertrue;}elseif(hhighest){bettertrue;}}}if(better){typesdiff.size();totaldepth1;highest0;vectorintvs;for(inti0;idepth;i){highestmax(highest,stamps[used[i]]);vs.push_back(stamps[used[i]]);}sort(vs.begin(),vs.end());best.push_back(vs);}return;}for(intiidx;in;i){used[depth]i;dfs(depth1,i,sumstamps[i]);}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intvalue;while(cinvalue){n0;stamps[n]value;while(cinvalue,value0)stamps[n]value;while(cinrequest,request0){best.clear();types0,total10,highest0;dfs(0,0,0);coutrequest;if(best.size()0)cout ---- none\n;else{cout (types):;if(best.size()1){for(inti0;ibest[0].size();i)cout best[0][i];cout\n;}elsecout tie\n;}}}return0;}总结本题通过深度优先搜索枚举所有不超过444张邮票的组合并按照多级优先级比较选出最优。关键点在于正确实现组合的生成和比较逻辑注意处理并列最优时输出tie。由于数据规模小暴力搜索完全可行。该解法体现了递归搜索和状态比较的基本技巧适合作为组合枚举的练习。