Algorithm –> 邮票连续组合问题

邮票组合问题

有四种面值的邮票很多枚，面值分别为1,4,12,21，取五张，求取出这些邮票的最大连续组合值

代码：

#include <stdio.h>
#include <string.h>
#define N 5
#define M 5
int k, Found, Flag[N];
int Stamp[M] = {, , , , };
// 在剩余张数n中组合出面值和Value
int Combine(int n, int Value)
{
　　if(n >=  && Value == )
　　{
  　　 Found = ;
  　　 int Sum = ;
  　　 for(int i=; i<N && Flag[i] != ; i++)
  　　 {
   　　 　　Sum += Stamp[Flag[i]];
   　　 　　printf("%d ", Stamp[Flag[i]]);
   　　}
  　　 printf("\tSum=%d\n\n", Sum);
　　}
　　else
 　{
　　  for(int i=; i<M && !Found && n>; i++)
  　　 if(Value-Stamp[i] >= )
  　　 {
  　　　　  Flag[k++] = i;
   　　　　 Combine(n-, Value-Stamp[i]);
  　　　　  Flag[--k] = ;
 　　  }
　　}
　　return Found;
}
int main(int argc, char* argv[])
{
   for(int i=; Combine(N, i); i++, Found=);
}

改进算法：

#include <iostream>
#include <string.h>
using namespace std;#define MAX 10
#define MAXINT 100000#define min(a, b) ((a) >= (b) ? (b) : (a))int Stamp[MAX+];
int StampCnt[MAXINT] = {};int MaxValue(int n, int m)
{
    int i, j;    for(i = ; ; i++)
    {
        StampCnt[i] = ;
        for(j = ; j <= m; j++)
        {
            if(Stamp[j] == i)
            {
                StampCnt[i] = ;
                break;
            }
            else if(i > Stamp[j])
            {
                StampCnt[i] = min(StampCnt[i], StampCnt[i-Stamp[j]] + );
            }
        }        if(StampCnt[i] > n)
            return i-;
    }
  //  return 0;
}int main()
{
    int N, M;
    int i, j;    cin >> N >> M;  //5 5， 输入 1 2 4 12 21， 输出 71    memset(Stamp, , sizeof(Stamp));
    for(i = ; i <= M; i++)
    {
        cin >> Stamp[i];
    }    cout << MaxValue(N, M) << endl;
}