贪心？？能解决吗？我要的是可行解的总数，而不是最优解

动态规划是可以做，我会，我只是想用不同的方法解决这个问题，穷举，回溯，动态规划这些太常见了

那我先来一个，这个是我们上课的时候老师给的代码，我自己写的不是很规范，所以就给老师的了
这是用递推做的

 #include<stdio.h>
void main()
{
    int p,i,j,m,n,k;
   static int x[12];
  static long int a[12][1001];
  long b,s;
  printf("请输入整币值(单位数):");            /* 输入处理数据 */
  scanf("%d",&m);
  printf("请输入零币种数:");
  scanf("%d",&n);
  printf("(从小至大依次输入每种零币值)\n");
  for(i=1;i<=n;i++)
     {
      printf("第%d种零币值(单位数):",i);
      scanf("%d",&x[i]);
  }
  for(i=0;i<=m;i++)                           /* 确定初始条件 */
      if(i%x[1]==0) a[1][i]=1; else a[1][i]=0;
  for(s=a[1][m],j=2;j<=n;j++)           /* 递推计算a(2,m),a(3,m),...*/
     {
      for(i=x[j];i<=m;i++)
     {
          p=i-x[j];b=0;
         for(k=1;k<=j;k++)
            b+=a[k][p];
            a[j][i]=b;}
            s+=a[j][m];
  }                     /* 累加a(1,m),a(2,m),...*/
  printf("整币兑零种数为:%ld\n",s);           /* 输出兑零种数 */
}