在現實生活中，經常遇到找零問題，假設有數目不限的面值為20,10,5,1的硬幣。
給出需要找零數，求出找零方案，要求：使用數目最少的硬幣。
對於此類問題，貪心算法采取的方式是找錢時，總是選取可供找錢的硬幣的最大值。比如，需要找錢數為25時，找錢方式為20+5，而不是10+10+5。
下面是C語言實現（DEV c++4.9.9.2運行通過）
[cpp]
#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:可供找零的面值種類數
* n:需要找零數
*/
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");
}
#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:可供找零的面值種類數
* n:需要找零數
*/
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");
}
需要說明的是，在一些情況下，找零錢問題使用貪心算法並不能得到整體最優解，其結果可能只是最優解的很好近似。
比如，如果提供找零的面值是11，5，1，找零15。
使用貪心算法找零方式為11+1+1+1+1，需要五枚硬幣
而最優解為5+5+5，只需要3枚硬幣。
