【题7】邮票面值的设计

【题7】邮票面值的设计给定一个信封，最多只允许粘贴n张邮票，计算在给定k(n+k≤20)种邮票的情况下（假设所有的邮票数量足够），如何设计邮票面值，能得到最大值max，使在1～max之间的每一枚邮票值都能得到：输入：NK输出：第一行为K个数，分别表示K种邮票面值第二行为max题解1.数据结构设now——面值序列。其中now[i]为第i种面值。各面值按递增顺序排列，长度为P(0≤P≤K)can——邮资序列。其中can[i]为邮资i得到的标志，邮资最大值为maxn(0≤i≤maxn)answer，best——最佳方案。其中answer[i]为最佳方案中第i种面值(1≤i≤k)，得到连续邮资的最大值为best；2.加入一枚邮票往当前邮资序列can[o]‥can[maxn]加入一枚邮票，形成一个新的邮资序列can’。由于该枚邮票的面值可能有P种(now[1]‥now[p])，因此，分别将这P种面值加入到目前存在的每一种邮资上：can’[j+now[i]]=true（can[j]=true，1≤i≤p，0≤j≤maxn）显然新邮资的最大值为maxn+now[p]。procedureget(p，varmaxn)；{计算所有邮资加入一枚邮票后得到的邮资序列。返回邮资最大值maxn}begint←can；fori←1topdo{搜索每一种面值}forj←0tomaxndo{搜索每一种邮资}ifcan[j]{若邮资j存在，则计算加入第i种面值的一枚邮票后得到的新邮资}thent[j+now[i]]←true；can←t；maxn←maxn+now[p]；{返回新邮资序列和邮资最大值}end；{get}3.回溯搜索最佳方案①当前状态p—目前得到的面值数。初始时P=0；last——目前得到的最大面值。初始时last=0；max——目前得到的连续邮资的最大值。初始时max=0；我们将p、last、max作为递归程序的值参，第p+1种面值的可能值i作为局部变量；②边界条件和最佳目标状态边界条件：p=k；(产生k种面值)最佳目标状态：maxbest(连续邮资的最大值为目前最佳)若上述条件满足，则记下最佳方案：best←max；answer←now；③搜索范围now序列中新增的面值i作为算符。按照面值升序的要求，i的取值范围last+1≤i≤max+1一旦枚举出新面值i(now[p+1]←i)，则计算n枚邮票可能得到的邮资序列can和其中连续邮资的最大值ma，并递归计算下一种面值：can[o]←true；forj←1tondoget(p+1，h)；{计算邮资序列can和最大邮资h}forj←1toh+1do{计算连续邮资的最大值ma}ifnotcan[j]thenbeginma←j-1；break；end；{then}递归计算子状态(p+1，i，ma)；由此得出递归程序：proceduresolve(p，last，max)；vari：integer；beginifp=k{若产生k种面值}thenbeginifmaxbest{若连续邮资的最大值为目前最佳，则记下最佳方案}thenbeginbest←max；answer←now；end；{then}exit；{回溯}end；{then}fori←last+1tomax+1do{搜索第p+1种面值的每一个可能值}beginnow[p+1]←i；h←0；fillchsr(can，sizeof(can)，false)；can[0]←true；{计算加入面值i后的邮资序列can和最大邮资h}forj←1tondoget(p+1，h)；forj←1toh+1do{计算连续邮资的最大值ma}ifnotcan[j]thenbeginma←j-1；break；end；{then}solve(p+1，i，ma)；{递归计算子状态}end；{for}end；{solve}1.主程序输入n，k；best←0；solve(0，0，0)；输出最佳方案中的面值序列answer[1‥k]和最大连续邮资best；