贪婪算法

352262

　　贪婪算法的基本思路：从问题的某一个初始解出发，逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出近似解。
　　由贪婪算法的特点和思路可以看出来，该算法存在以下问题：
　　1.不能保证最后的解是最优的
　　2.不能用来求最大或者最小解问题
　　3.只能求满足某些约束条件的可行解范围。
　　实例，找零钱。



#include <stdio.h>
#define MAXN 9
int parvalue[MAXN] = {10000,5000,1000,500,200,100,50,20,10};
int num[MAXN] = {0};
int exchange(int n){
int i, j;
for(i=0; i<MAXN; i++){
if(n>parvalue){
break;//先找到比n小的最大面额
        }
}
while(n>0 && i<MAXN){
if(n>=parvalue){
n -= parvalue;
num++;
}
else if(n<10 && n>=5){
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>0){
printf("%6.2f：%d张\n",(float)parvalue/100.0,num);
}   
}
getch();
return 0;
}