当前位置 博文首页 > ice_elephant的博客：数据结构算法之贪心算法
贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有
利)的选择，从而希望能够导致结果是最好或者最优的算法。
请看下面案例，假设有如下课程，希望尽可能多的将课程安排在一间教室里：
课程 开始时间 结束时间
美术 9:00 10:00
英语 9:30 10:30
数学 10:00 11:00
计算机 10:30 11:30
音乐 11:00 12:00
这个问题看似要思考很多，实际上算法很简单:
#include<stdio.h>
#include<Windows.h>
//贪心算法
#define N 7
//钱的面值
int value[]={1,2,5,10,20,50,100};
int Count[]={10,2,3,1,2,3,5};
int greedy(int Money){
//采取的方法是每一张面值都进行比较，然后结束条件是要么剩余的money小于0，要么钱数完了money还不为零就结束了
int num=0;
//从面值最大的开始
for(int i=N-1;i>=0;i-- ){
int c = Money/value[i]; //计算出需要几张这样的面值
num = c>Count[i]?Count[i]:c; //如果需要的面值数量大于该面值数量直接返回该面值数量否则返回c
printf("需要面值为:%d的%d张\n",value[i],num);
Money-=value[i]*num;
if(Money==0) break;
}
if(Money!=0) num=-1;
return num;
}
int main(){
if(greedy(155)==-1){
printf("数额无法找开.\n");
}
system("pause");
return 0;
}
