文档介绍：找零钱问题的贪心算法问题描述:当前有面值分别为2角5分,1角,5分,1分的硬币,请给出找n分钱的最佳方案(要求找出的硬币数目最少)问题分析:根据常识,我们到店里买东西找钱时,老板总是先给我们最大面值的,要是不够再找面值小一点的,直到找满为止。如果老板都给你找分数的或者几角的,那你肯定不干,另外,他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。问题的算法设计与实现:先举个例子,假如老板要找给我99分钱,他有上面的面值分别为25,10,5,1的硬币数,为了找给我最少的硬币数,那么他是不是该这样找呢,先看看该找多少个25分的,99/25=3,好像是3个,要是4个的话,我们还得再给老板一个1分的,我不干,那么老板只能给我3个25分的拉,由于还少给我24,所以还得给我2个10分的和4个1分。具体实现//找零钱算法//Byfalcon//输入:数组m,依次存放从大到小排列的面值数,n为需要找的钱数,单位全部为分//输出:数组num,对照数组m中的面值存放不同面值的硬币的个数,就找钱方案publicstaticint[]zhaoqian(intm[],intn){intk=;int[]num=newint[k];for(inti=0;i<k;i++){num=n/m;n=n%m;}returnnum;}lasszhaoqian{publicstaticvoidmain(String[]args){intm[]={25,10,5,1};intn=99;int[]num=newint[];num=zhaoqian(m,n);(n+"的找钱方案:");for(inti=0;i<;i++)(num+"枚"+m+"面值");}publicstaticint[]zhaoqian(intm[],intn){intk=;int[]num=newint[k];for(inti=0;i<k;i++){num=n/m;n=n%m;}returnnum;}}#include<>#include<>#defineM10usingnamespacestd;intCoinsbackup[6];intCoin_Face[6]={5,10,20,50,100,200};intNumber_of_Money(intCoins[6],intCoin_Face[6],doubleX,intY,intZ){intback1[6]={5,10,20,50,100,200};intback2[11]={15,25,30,40,55,60,70,105,110,120,150};intback3[13]={35,45,65,75,80,90,115,125,130,140,155,160,170};intback4[8]={85,95,135,145,165,175,180,190};intback5[2]={185,195};inti;for(i=1;i>0;i++){intj=0;loop2:for(j;j<i;j++){intm=5,n=i-j,a,b=0;switch(j){case0:Y=(int)(100*X);for(a=0;a<6;a++){Coins[a]=Coinsbackup[a];}while(Coins[m]==0||Y<Coin_Face[m]){m--;}while(Coins[m]!=0&&Y>=Coin_Face[m]&&m!=-1){Y=Y-Coin_Face[m];Coins[m]=Coins[m]-1;n=n-1;if(Y==0&&n==0)gotoloop1;elseif((Y==0&&n!=0)||(Y!=0&&n==0)){j=j+1;gotoloop2;}while(Coins[m]==0||Y<Coin_Face[m]){m--;if(m<0)break;}}break;loop3:case1:m=5;n=i-j;for(b;b<6;b++)Z=back1[b];Y=(int)(100*X)+Z;for(a=0;a<6;a++){Coins[a]=Coinsbackup[a];}while(Coins[m]==0||Y<Coin_Face[m]){m--;}while(Coins[m]!=0&&Y>=Coin_Face[m]&&m!=-1){Y=Y-Coin_Face[m];Coins[m]=Coins[m]-1;n=n-1;if(Y==0&&n==0)gotoloop1;elseif((Y==0&&n!=