C语言：无限硬币的最少钱币数问题

C语言：无限硬币的最少钱币数问题

问题：这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑 15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。
你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。
【要求】（代码需加注释）
【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。
【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。
【样例输入】
15
6 2 5 10 20 50 100
1
1 2
0
【样例输出】
2
Impossible

分析：硬币数最少，大家脑海中立马想到的肯定是从面额最大的开始依次往前匹配，但这样就面临一些特殊情况，类似硬币面额1，9，10，要凑的钱数为18，那么最少钱币数应该是2个，但输出结果却是9。所以我们可以再加一个循环（每次匹配完，得到一个钱币数之后，再去掉一个最大面额硬币），然后初始化，再次进行匹配，比较每次匹配后的钱币数，取最小值。

#include <stdio.h>
#define N 12
int M,K;//M是要凑成的钱数，K是硬币的种类数
int coin[N];//存放硬币面额的数组
int count=100;//用于记载凑够所需硬币个数
int i,j;
void input(){//输入函数scanf("%d",&M);scanf("%d",&K);for(i=0;i<K;i++){scanf("%d",&coin[i]);}
}
void paixu(){//将数组中硬币面额按从小到大的顺序排列int emp;for(i=0;i<K;i++){for(j=0;j<K-i-1;j++){if(coin[j]>coin[j+1]){emp=coin[j];coin[j]=coin[j+1];coin[j+1]=emp;}}
}	
}
int min(int x,int y){//取两个数中的最小值if(x<y)return x;else return y;
}int main(){printf("input\n");input();paixu();int m,sum;//m用来复制M中的数值，sum用来统计硬币数for(i=K-1;i>=0;i--){//第一个for循环：每进行一次下面的匹配过程就去掉一个最大值，然后再重新进行匹配，防止漏掉一些特殊的情况sum=0;//初始化sum和mm=M;for(j=i;j>=0;j--){//第二个for循环从最大值开始依次往前匹配if(m%coin[j]==0){sum+=m/coin[j];m=m%coin[j];break;}else{sum+=m/coin[j];m=m%coin[j];}}if(m==0)count=min(count,sum);}while(M!=0){//输入M=0，结束并输出结果，这个是为了题目中要求M=0时结束加的。scanf("%d",&M);}printf("Output:\n");if(count==100)printf("impossible!\n");else{printf("%d\n",count);}return 0;
}

输入题目中的数据得出结果：

输入其他数据：

第四行输入0是结束并输出结果的意思，为了顺应题目要求。

第一次写博客，多有不足，望大家体谅。