回溯连续邮资问题

---

---

假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。 例如当n=5，m=4时，面值为1，3，11，15，32的5种邮票可以贴出邮资的最大连续区间是1到70。

分析：

有一个难点：最大可以贴n张邮票，也就是说1、2...n张都可以，究竟帖多少张是不固定的，但我们可以构造面值是0的邮票，差几张就加几张面值为0的票，目的是让贴的邮票数量成为一个定值，便于解答
　　既然是回溯解决，自然想t代表什么。一般来说，t要么代表邮票数量，要么代表增长的区间的值，但是区间最大值究竟是多少是不知道的，无法写终止条件。
　　贴邮票的数量已经通过面值0的邮票这一手段使它变成了一个定值，t就只能代表邮票数量了。

代码：

#include<stdio.h>
#define n 6      //邮票的面值种类加1，因为还要添加面值为0的邮票 
#define m 4      //最多贴m张邮票
int money=0,tmoney=0;   //money是连续区间的上限;  tmoney是过程值
int a[n]={0,1,3,11,15,32}; 
bool flag;

void traceback(int t){
    if(t==m){
        if(tmoney==money+1)
            flag=true;
        return;
    }   
    for(int i=0;i<n;i++){
        tmoney+=a[i];
        if(tmoney<=money+1)
            traceback(t+1);
        tmoney-=a[i];
    }   
}

int main(){
    while(true){ //最大值为多少，不知道，需不断循环确定
        flag=false;
        traceback(0);     //t代表邮票的数量 
        if(flag)
            money++;
        else
            break;
    }   
    printf("%d",money); 
    return 0;
} 

运行截图