连续邮资问题

连续邮资问题

---

Time Limit:1s	Memory limit:32M
Accepted Submit:88	Total Submit:220

---

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

数据输入:
输入数据每一行给出2个正整数m和n的值（1<=n，m<=9），最后以0 0 表示文件结束。

结果输出:
对于输入中每一行的正整数m和n，将最大连续邮资区间输出。

样例输入

4 5
0 0

样例输出

70

#include<stdio.h>
#include<string.h>

#define MAX_VAL(x, y) (((x) > (y)) ? (x) : (y))
#define MIN_VAL(x, y) (((x) < (y)) ? (x) : (y))

int n, m;
int coins[20];
int letter[10000];
int r;

int check(int num)
{
    int i;
    int v;
    int maxv;
    
    maxv = coins[num];
    while (1)
    {
        v = 1000;
        for (i = 1; i <= num; ++i)
        {
            if (maxv - coins[i] < 0)
                continue;
            v = MIN_VAL(v, letter[maxv - coins[i]]);
        }
        if (v >= m)
            break;
        letter[maxv] = v + 1;
        ++maxv;
    }

    return maxv - 1;
}

int search(int num, int maxv)
{
    int i, r;
    int val;

    if (num >= n)
        return maxv;

    val = 0;
    for (i = maxv + 1; i >= coins[num] + 1; --i)
    {
        //if (num + 1 == n && i * m <= val)

            //continue;

        coins[num + 1] = i;
        r = check(num + 1);
        r = search(num + 1, r);
        val = MAX_VAL(r, val);
    }

    return val;
}

int main()
{
    int val;
    int i;

    while (scanf("%d %d", &m, &n) && m)
    {
        coins[1] = 1;
        for (i = 0; i <= m; ++i)
            letter[i] = i;
        val = search(1, m);
        printf("%d\n", val);
    }
    
    return 0;
}