Stamps uva+回溯 Stamps

Stamps

The government of Nova Mareterrania requires that various legaldocuments have stamps attached to them so that the government canderive revenue from them. In terms of recent legislation, each classof document is limited in the number of stamps that may be attached toit. The government wishes to know how many different stamps, and ofwhat values, they need to print to allow the widest choice of valuesto be made up under these conditions. Stamps are always valued inunits of $1.

This has been analysed by government mathematicians who have derived aformula for n(h,k), where h is the number of stamps that may beattached to a document, k is the number of denominations of stampsavailable, and n is the largest attainable value in a continuoussequence starting from $1. For instance, if h=3, k=2 and thedenominations are $1 and $4, we can make all the values from $1 to$6 (as well as $8, $9 and $12). However with the same values of hand k, but using $1 and $3 stamps we can make all the values from$1 to $7 (as well as $9). This is maximal, so n(3,2) = 7.

Unfortunately the formula relating n(h,k) to h, k and the values ofthe stamps has been lost--it was published in one of the governmentreports but no-one can remember which one, and of the threeresearchers who started to search for the formula, two died of boredomand the third took a job as a lighthouse keeper because it providedmore social stimulation.

The task has now been passed on to you. You doubt the existence of aformula in the first place so you decide to write a program that, forgiven values of h and k, will determine an optimum set of stamps andthe value of n(h,k).

Input

Input will consist of several lines, each containing a value for h andk. The file will be terminated by two zeroes (0 0). For technicalreasons the sum of h and k is limited to 9. (The President lost hislittle finger in a shooting accident and cannot count past 9).

Output

Output will consist of a line for each value of h and k consisting ofthe k stamp values in ascending order right justified in fields 3characters wide, followed by a space and an arrow (

->

) and the valueof n(h,k) right justified in a field 3 characters wide.

Sample input

3 2
0 0      

Sample output

1  3 ->  7      

解决方案：具体题意，最多有k种不同的面值的邮票，最多贴h张邮票，要求组合成1到Max连续的值的邮票，求能得到的最大的Max是多少，并输出用的邮票的面值。

首先，面值1的必需要的，因为没有面值1的就没有1值得邮票，当只选1的情况是最大Max是h，然后到下一个，取值范围：[前一个面值+1，前一次的Max+1]，为什么要取到‘前一次的Max+1’呢？应为比这个值大的时候，就会出现段层，不连续了。剩下的就是递归回溯的问题了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int h,k;
int Max;
int L[10000];
int ans[10000];
int MaxL[10000];
bool curr[10000];
void dfs(int x,int n,int sum){

    if(x>=h)
        {curr[sum]=true;
    return ;}
    curr[sum]=true;
    for(int i=0;i<=n;i++){
        dfs(x+1,n,sum+L[i]);
    }
}///求出当前面值组合能组成的连续的1到Max值，也是递归思路求法。
void Se(int cur){

    if(cur>=k){
        if(MaxL[cur-1]>Max){
          {
            Max=MaxL[cur-1];
            memcpy(ans,L,sizeof(L));
          }
        }///更新Max，和ans。
        return ;
    }
    for(int i=L[cur-1]+1;i<=MaxL[cur-1]+1;i++){
        L[cur]=i;
        memset(curr,0,sizeof(curr));
        dfs(0,cur,0);
        int j=1,num=0;
        while(curr[j++]) num++;
        MaxL[cur]=num;///把每种组合的Max存入MaxL数组，以便下次确定面值取值范围
        Se(cur+1);
    }///用递归枚举每种情况，相当于深搜树。


}
int main(){

   while(~scanf("%d%d",&h,&k)&&(h+k)){
    memset(L,0,sizeof(L));
    memset(curr,false,sizeof(curr));
    L[0]=1;
    Max=h;
    MaxL[0]=h;
    Se(1);
    for(int i=0;i<k;i++){
        printf("%3d",ans[i]);

    }
     printf(" ->%3d\n",Max);
   }
   return 0;
}