贪心算法经典例题讲解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 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;

}