所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步
do 求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include "stdio.h"
void main()
{
int act[11][3]={{1,1,4},{2,3,5},{3,0,6},{4,5,7},{6,5,9},
{7,6,10},{8,8,11},{9,8,12},{10,2,13},{11,12,14}};
greedy(act,11);
getch();
}
int greedy(int *act,int n)
{
int i,j,no;
j=0;
printf("Selected activities:/n");
no=0;
printf("Act.%2d: Start time %3d, finish time %3d/n", act[no],act[no+1],act[no+2]);
for(i=1;i<n;i++)
{
no=i*3;
if(act[no+1]>=act[j*3+2])
{
j=i;
printf("Act.%2d: Start time %3d, finish time %3d/n", act[no],act[no+1],act[no+2]);
}
}
}
|
例题
题目描述：
又到毕业季，很多大公司来学校招聘，招聘会分散在不同时间段，小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。
输入：
第一行n，有n个招聘会，接下来n行每行两个整数表示起止时间，由从招聘会第一天0点开始的小时数表示。
n <= 1000 。
输出：
最多参加的招聘会个数。
样例输入：
3
9 10
10 20
8 15
样例输出：
2
活动选择问题
概述
这个问题是对几个相互竞争的招聘会活动进行调度，它们都要求以独占的方式使用某一公共资源（小明）。调度的目标是找出一个最大的相互兼容的活动集合。这里是有一个需要使用某一资源（小明）的n个活动组成的集合S={a1,a2,...,an}.该资源一次只能被一个活动占用。每个活动ai有开始时间si和结束时间fi，且0<=si<fi<无穷。一旦被选择后，活动ai就占据了区间[si,fi].如果区间[si,fi]和[sj,fj]互不重叠，称活动ai和aj是兼容的。活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。
将所有的活动按照结束时间升序排列
定理
对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动：
fm=min{fk:ak属于Sij}
那么，
1）活动am在Sij的某最大兼容活动子集中被使用
2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题
ac代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct join
{
int begin;
int end;
};
int compare(const void *a, const void *b);
int main()
{
int i, n, k;
struct join joins[1001], temp[1001];
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i ++)
{
scanf("%d %d", &joins[i].begin, &joins[i].end);
}
qsort(joins, n, sizeof(joins[0]), compare);
k = 0;
temp[k] = joins[0];
for(i = 1; i < n; i ++)
{
if(joins[i].begin >= temp[k].end)
temp[++ k] = joins[i];
}
printf("%d\n", k + 1);
}
return 0;
}
int compare(const void *a, const void *b)
{
const struct join *p = a;
const struct join *q = b;
return p->end - q->end;
}
|
/**************************************************************
Problem: 1463
User: wangzhengyi
Language: C
Result: Accepted
Time:10 ms
Memory:904 kb
****************************************************************/