在現(xiàn)實(shí)生活中，經(jīng)常遇到找零問(wèn)題，假設(shè)有數(shù)目不限的面值為20,10,5,1的硬幣。 給出需要找零數(shù)，求出找零方案，要求：使用數(shù)目最少的硬幣。
對(duì)于此類問(wèn)題，貪心算法采取的方式是找錢時(shí)，總是選取可供找錢的硬幣的最大值。比如，需要找錢數(shù)為25時(shí)，找錢方式為20+5，而不是10+10+5。
下面是C語(yǔ)言實(shí)現(xiàn)（DEV c++4.9.9.2運(yùn)行通過(guò)）
#include<stdio.h>void greedyMoney(int m[],int k,int n);int main(void) {int money[] = {20,10,5,1};int k;k = sizeof(money)/sizeof(money[0]); greedyMoney(money,k,25);system("PAUSE"); }/* * m[]:存放可供找零的面值，降序排列 * k:可供找零的面值種類數(shù) * n:需要找零數(shù) */ void greedyMoney(int m[],int k,int n) {int i;for(i=0;i<k;i++){while(n>=m[i] && n>0){printf("%d.",m[i]); n = n-m[i];}} printf("\n");}
需要說(shuō)明的是，在一些情況下，找零錢問(wèn)題使用貪心算法并不能得到整體最優(yōu)解，其結(jié)果可能只是最優(yōu)解的很好近似。 比如，如果提供找零的面值是11，5，1，找零15。 使用貪心算法找零方式為11+1+1+1+1，需要五枚硬幣 而最優(yōu)解為5+5+5，只需要3枚硬幣。

總結(jié)

以上是生活随笔為你收集整理的找零钱问题（C语言实现）——贪心算法应用（1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。