邮票面值的设计.docx

【题7】邮票面值的设计

给定一个信封，最多只允许粘贴n张邮票，计算在给定k(n+k≤20)种邮票的情况下（假设所有的邮票数量足够），如何设计邮票面值，能得到最大值max，使在1～max之间的每一枚邮票值都能得到：

输入：

N K

输出：

第一行为K个数，分别表示K种邮票面值第二行为max

题解

数据结构

设

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；

加入一枚邮票

往当前邮资序列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}

回溯搜索最佳方案

①当前状态

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]thenbegin ma←j-1； break；end；{then}

递归计算子状态(p+1，i，ma)；

由此得出递归程序：

procedure solve(p，last，max)；vari：integer；

begin

ifp=k {若产生k种面值}

thenbegin

ifmaxbest {若连续邮资的最大值为目前最佳，则记下最佳方案}thenbeginbest←max； answer←now；end；{then}

exit； {回溯}

end；{then}

fori←last+1tomax+1do {搜索第p+1种面值的每一个可能值}begin

now[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；