资源描述：
《连续邮资问要求对于给定的n和m的值,给出邮票面值的.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、假设某国家发行了n种不同面值的邮票并且规定每张信封上最多只允许贴m张.连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,使得可在1张信封上贴出从邮资1开始,增量为1的最大连续邮资区间.例如:当n=5,m=4时,面值为(1,3,11,15,32)的五种邮票可以贴出邮资的最大连续邮资区间是1到70.当时选拔赛我就这道题没做上,现在还是不会,请高手指点.听说要用回朔法,不过我还是不会.请把算法说清楚.这个题就是搜啊搜啊，剪啊剪啊：）呵呵～～～～不过俺这方面不强，以前做的程序也不够快，这个题海星大哥发给过我他做的东西，虽然我还
2、留着，不过就让海星大哥贴他的解析吧：）不过我看这好象刘汝佳没来（他喜欢ＩＤ就用自己名），而我也见过他站上写的这个东西的解析，贴出来看看吧：）*****************************第四题邮票面值设计（40分）给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k<=40)种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max，使得1－max之间的每一个邮资值都能得到。例如，N=3，K＝2，如果面值分别为1分、4分，则在l分-6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）
3、：如果面值分别为1分、3分，则在1分-7分之间的每一个邮资值都能得到。可以验证当N=3，K＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。样例：INPUTN=3k=2OUTPUT13MAX=7不知同学们第一个感觉是不是递推？反正我当时是。我想了一会儿，发现递推是行不通的，然后一个很自然的思路就是搜索。当时我很不想用搜索，因为上限是K=40,N=40,但后来才知道这是出题者的一个疏忽，根本不可能在时限内到40的。从下面的测试数据中也可以看出来。解状态是一个K元组(v1,v2,v3..vk),不妨设：v
4、1v[p],而若v[p]>=R+2,则R+1根本不可能取到。递归搜索就可以了。本题的难点是如何计算最大连续值（以下成为Q值）。一个容易想到的方法是枚举所有的取法，求出可以取到的最大值，再求Q值，简单，但是效率不高。以下是供参考的递推其他方法：递推求Q值，保存前P个面值用1,2,3..K张可以取得的值，再加上第P+1张取与不取的情况可以得到前P+1个面值用1,2,3..K张可以取得的值。即，用T张前P个面值能得到S,用T+1张前P+1个面值可以得到S+V[P+1],用T张前P+1个面值也能得到S.为了使程序易懂，我采用的是简单的方法
5、，效率低一些，但是好懂一些。以下我竞赛时写的程序，后来加了很多注释，将就看一下吧！我先把可能不好懂的地方说一下：1.Cont(x)就是前x个元素的Q值2.Find(Findstart,Contstart,x);x:当前搜索的邮票序号，findstart:第x张邮票的最小可能值（搜索起点），Contstart:需要从Contstart开始连续取值（也就是：前x-1张可以从1取到Contstart-1）OK，Hereitis:{$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,R-,S-,V+,X-}{$M65520,0,
6、655360}ProgramStamp;ConstMaxn=40;VarValue,BestValue:Array[1..Maxn]OfInteger;Max,N,K:Integer;{IfN=5,K=5Value[]=(1,4,9,31,51),Itreturns126,Gotit?}FunctionCont(x:Integer):Integer;VarI:Integer;CanGet:Array[0..10000]OfBoolean;Count:Array[1..Maxn]OfInteger;ProcedureUseIt(Nu
7、m,Left:Integer);VarI:Integer;Total:Integer;BeginIfNum=x+1ThenBeginTotal:=0;ForI:=1toxDoInc(Total,Value[i]*Count[I]);CanGet[Total]:=True;Exit;End;ForI:=0toLeftDoBeginCount[Num]:=I;UseIt(Num+1,Left-I)End;End;BeginFillchar(CanGet,SizeOf(CanGet),0);UseIt(1,n);I:=1;WhileCa
8、nGet[i]DoInc(I);Cont:=I-1;End;(*Thisisthemostimportantparteg:N=3,K=3Supposewe'researchingforthe3rdstampwhilethefirsttwoare1,
