最少硬币

 一、 问题描述： 设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。 输入   输入的第一行中只有1 个整数给出n的值,第2 行起每行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。 输出   程序运行结束时，将计算出的最少硬币数输出。问题无解时输出-1。 二|、问题分析 根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。 问题的算法设计与实现： 先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分，由于还少给我24，所以还得给我2个10分的和4个1分。 三、程序实现 //找零钱算法 //By falcon //输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分 //输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，即找钱 四、程序代码： #include int T[11],Coins[11],n; int c[20002],num[20002]; int main(int argc, char* argv[]) { int i,j,m; scanf("%d",&n); for(i=0;i