数据结构和算法-贪婪算法
1、算法名称：贪婪算法2、算法思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中某一步不能再向前继续前进时，就停止算法，给出近似解
3、该算法存在的主要问题
1、不能保证最后的解释最优的
2、不能用来求最大或最小解的问题
３、只能求满足某些约束条件的可行解的范围
4、实例：
在买东西找零钱的时候，有多种找零钱的方式可以采取。如果按照贪婪算法是按照面值由大到小的顺序来找零的、
代码：
[*]#include<stdio.h>
[*]#define MAXN 9
[*]int parvalue={10000,5000,1000,500,200,100,50,20,10};
[*]int num={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++;
[*] break;
[*] }else i++;
[*] }
[*] }
[*] return 0;
[*]}
[*]int main()
[*]{
[*]int i;
[*]float m;
[*]printf("请输入找零的金额");
[*]scanf("%f",&m);
[*]exchange((int)100*m);
[*]printf("\n%0.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;
[*]}
程序运行结果
附件列表
页:
[1]