贪心算法经典例题讲解c语言简单
贪心算法是一种常见且实用的算法思想，可以在不用考虑所有情况的情况下对复杂问题进行求解。本文将以贪心算法经典例题为例，介绍贪心算法的基本思想和步骤，并用C语言代码实现。
一、基本思想
贪心算法是一种直觉性解题策略，在解决某些最优化问题时，贪心算法作出的选择是当前状态下最优的选择，即所做出的选择不依赖于以后的选择或者状态，而是只与当前的状态有关。
二、步骤
贪心算法的步骤如下：
1.建立所求问题的模型；
2.基于当前状态，选择局部最优策略；
3.通过所选的局部最优策略，得到全局最优解。
三、例题讲解
下面以每日最大开心值为例，详细讲解贪心算法的思想和步骤。每个人有一份工作表，上面记录着在每天结束时可以获得的最大开心值和需要工作的天数。每位员工每天只能选择一份工作，工作结束后，无法更改。问如何让员工获得最大开心值。（类似背包问题）
假设输入数据如下：
1 3 #第一项 每个工作的天数及价值
2 5
3 1
4 6
4 3 #第二项 员工人数和工作天数
5 3
6 8
7 5
针对此问题，我们可以得出以下的结论：先干需要工作天数短或开心值高的工作，每次选择开心值最大的工作。
下面给出由C语言实现的贪心算法代码（一般全部正确，部分有点关于输出）
#include
#define COUNT 1000
struct job
{
int time;
int value;
}j[COUNT];
int time = 0,value = 0;
//比较函数
int cmp(const void *a,const void *b)
{
return (*(struct job*)b).value<(*(struct job*)a).value?-1:1;
}
int main()
{
int i,jobs,workers;
scanf("%d%d",&jobs, &workers);
for(i=0; i
{
scanf("%d%d",&j[i].value,&j[i].time);
}
//C语言自带的quick sort排序
qsort(j,jobs,sizeof(j[0]),cmp);
for(i=0; i
{
int day,now=0;
scanf("%d",&day);
//选择开心值最大的工作
for(j=0; j
{
if(j[j].time<=day)
{
now=j[j].value;
day-=j[j].time;
value+=now;
}
}
time+=day*now;
}
printf("%d\n",value);
return 0;
}
