找零钱问题的贪心算法

《找零钱问题的贪心算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、找零钱问题的贪心算法问题描述：当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）问题分析：根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。问题的算法设计与实现：先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，99／25＝3，好像是3个，要是4个的话，我

2、们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。具体实现//找零钱算法//Byfalcon//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案publicstaticint[]zhaoqian(intm[],intn){intk=m.length;int[]num=newint[k];for(inti=0;i=n/m;n=n%m;}returnnum;}publicclas

3、szhaoqian{publicstaticvoidmain(String[]args){intm[]={25,10,5,1};intn=99;int[]num=newint[m.length];num=zhaoqian(m,n);System.out.println(n+"的找钱方案：");for(inti=0;i+"枚"+m+"面值");}publicstaticint[]zhaoqian(intm[],intn){intk=m.length;int[]num=newint[k];for(inti

4、=0;i=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,

5、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

6、hile(Coins[m]==0

7、

8、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)

9、

10、(Y!=0&&n==0)){j=j+1;gotoloop2;} while(Coins[m]==0

11、

12、Y

13、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

14、

15、Y=Coin_Face[m]&&m!=-1) {Y=Y-Coin_Face[m]; Coins[m]=Coins[m]-1; n=n-1; if(Y==0&&n==0)goto