邮票面值设计

【问题描述】 【描述 Description 】 　　给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。 例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。 【样例输入】 共一行，两个整数，分表为N与M的值。 【输入格式 Input Format 】 一行，分别为N,M。 【输出格式 Output Format 】 两行。 第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。 第二行为最大值。 【样例输入 Sample Input 】 3 2 【样例输出 Sample Output 】 1 3 MAX=7 算法分析 深搜加DP 栈记录所用邮票的面值 每次面值的搜索的范围为：上一次使用的邮票面值+1 to 上一次连续达到的最大值+1 然后DP，记录达到每个面值用的最少邮票数，不断更新最优解 注意要从第1张邮票开始，否则要出错 【代码】

#include 

int a[11], ans[11];
int b[1001];
int n, m, max;

int dp(int i)
{
       int j, k;

       for (j = 1; j < 1001; j++)
              b[j] = 9999;

       for (j = 1; j <= i; j++)
              b[a[j]] = 1;
       j = 0;

       do
       {
              j++;

              for (k = 1; k <= i; k++)
                     if (j > a[k] && b[j - a[k]] + 1 < b[j])
                            b[j] = b[j - a[k]] + 1;

       }while (b[j] <= m);
       return j;
}

void search(int i)
{
       int j, k;

       if (i > n)
       {
              if (dp(i - 1) - 1 > max)
              {
                     for (j = 1; j <= 10; j++)
                            ans[j] = a[j];
                     max = dp(i - 1) - 1;
              }
              return;
       }
       j = dp(i - 1);

       for (k = j ; k >= a[i - 1] + 1; k--)
       {
              a[i] = k;
              search(i + 1);
       }
}

int main()
{

       int i;
       scanf("%d%d", &m, &n);

       max = 0;
       a[1] = 1;
       search(2);

       for (i = 1; i <= n; i++)
              printf("%d ", ans[i]);

       printf("\n");
       printf("MAX=%d\n", max);
       return 0;
}