165-Stamps【回溯】

回溯

给h和k的意思是在k种邮票中选h个邮票

基本的连续邮资问题

15226160

165

Stamps

Accepted

C++

0.062

2015-03-27 07:21:37

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 222;
const int maxd = 15;
int h,k;
int vis[maxn];
int array[maxd];
int ans_value;
int ans_array[maxd];
void dfs(int step,int arr[],int size,int sum){
    vis[sum] = 1;
    if(step == h){
        return;
    }
    for(int i = 0; i < size; i++)
        dfs(step + 1,arr,size,sum + arr[i]);
}
void dfs2(int step,int pos,int arr[]){
    dfs(0,arr,step,0);
    int next;
    for(int i = 1; ; i++)
        if(!vis[i]){
            next = i;
            break;
        }
    if(step == k){
        if(next - 1 > ans_value){
            for(int i = 0; i < step; i++)
                ans_array[i] = arr[i];
            ans_value = next - 1;
        }
        return;
    }
    int vis_temp[maxn];
    memcpy(vis_temp,vis,sizeof(vis));
    for(int i = pos; i <= next; i++){
        arr[step] = i;
        dfs2(step + 1,i + 1,arr);
        memcpy(vis,vis_temp,sizeof(vis_temp));
    }
}
int main(){
    while(scanf("%d%d",&h,&k) && h){
        memset(vis,0,sizeof(vis));
        array[0] = 1;
        ans_value = 0;
        dfs2(1,2,array);
        for(int i = 0; i < k; i++)
            printf("%3d",ans_array[i]);
        printf(" ->%3d\n",ans_value);
    }
    return 0;
}