贪婪算法

算法思路：
贪婪算法基本思路 : 从问题的某一个初始解出发逐步逼近给定的目标，以尽快可能快地求得更好的解。
当达到算法中的某一步不能再继续前进时，就停止算法，给出近似解。
该算法存在以下问题:

• 不能保证最后的解是最优的。
• 不能用来求最大或最小解问题。
• 只能求满足某些约束条件的可行解的范围

例题:

代码如下:

#include<stdio.h>
#define MAXN 9
int parvalue[MAXN]={10000,5000,1000,500,200,100,50,20,10};
//100 50 10 5  2   1  0.5 0.2 0.1
int num[MAXN]={0};
int exchange(int n)
{
	int i,j;
	for(i=0;i<MAXN;i++)
		if(n>parvalue[i])break;//找到比n小的最大面额
	while( n>0 && i<MAXN )
	{
		if(n>=parvalue[i])
		{
			n=n-parvalue[i];
			num[i]++;
		}
		else if(n<10 && n>=5)// 0.05<n<0.1 
		{
			num[MAXN-1]++;
			break;
		}
		else
		i++;
	}
	return 0;
}
int main(void)
{
	int i;
	float m;
	printf("请输入要找零的金额: ");
	scanf("%f",&m);
	exchange((int)100*m);
	printf("\n%.2f元零钱的组合为:\n",m);
	for(i=0;i<MAXN;i++)
	{
		if(num[i]>0)
			printf("%6.2f: %d张\n",(float)parvalue[i]/100.0,num[i]);
	}
	return 0;
}