給定乙個信封，最多隻允許貼上n張郵票，計算在給定k(n+k≤20)種郵票的情況下（假設所有的郵票數量足夠），如何設計郵票面值，能得到最大值max，使在1～max之間的每一枚郵票值都能得到：
輸入：n k
輸出：第一行為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]。
procedure get(p，var maxn)；
begin
t←can；
for i←1 to p do搜尋每一種面值}
for j←0 to maxn do搜尋每一種郵資}
if can[j若郵資j存在，則計算加入第i種面值的一枚郵票後得到的新郵資}
then t[j+now[i]]←true；
can←t； maxn←maxn+now[p返回新郵資序列和郵資最大值}
end；
3.回溯搜尋最佳方案
①當前狀態
p—目前得到的面值數。初始時p=0；
last——目前得到的最大面值。初始時last=0；
max——目前得到的連續郵資的最大值。初始時max=0；
我們將p、last、max作為遞迴程式的值參，第p+1種面值的可能值i作為區域性變數；
②邊界條件和最佳目標狀態
邊界條件： p=k產生k種面值)
最佳目標狀態： max>best連續郵資的最大值為目前最佳)
若上述條件滿足，則記下最佳方案：best←max；answer←now；
③搜尋範圍
now序列中新增的面值i作為算符。按照面值公升序的要求，i的取值範圍
last+1≤i≤max+1
一旦列舉出新面值i(now[p+1]←i)，則計算n枚郵票可能得到的郵資序列can和其中連續郵資的最大值ma，並遞迴計算下一種面值：
can[o]←true；
for j←1 to n do get (p+1，h計算郵資序列can和最大郵資h}
for j←1 to h+1 do計算連續郵資的最大值ma}
if not can[j]then begin ma←j-1； break；end；
遞迴計算子狀態(p+1，i，ma)；
由此得出遞迴程式：
procedure solve (p， last， max)；
var i：integer；
begin
if p=k若產生k種面值}
then begin
if max>best若連續郵資的最大值為目前最佳，則記下最佳方案}
then begin best←max； answer←now； end；
exit回溯}
end；
for i←last+1 to max+1 do搜尋第p+1種面值的每乙個可能值}
begin
now[p+1]←i； h←0；
fillchsr (can， sizeof(can)， false)；
can[0]←true計算加入面值i後的郵資序列can和最大郵資h}
for j←1 to n do get(p+1，h)；
for j←1 to h+1 do計算連續郵資的最大值ma}
if not can[j] then begin ma←j-1； break； end；
solve (p+1， i， ma遞迴計算子狀態}
end；
end；
● 主程式
輸入n， k；
best←0；
solve(0， 0， 0)；
輸出最佳方案中的面值序列answer[1‥k]和最大連續郵資best；