《算法导论》学习总结 — 22.第16章 贪心算法(2) 案例分析之活动选择问题

建议先看看前言:http://www.wutianqi.com/?p=2298

连载总目录:http://www.wutianqi.com/?p=2403

题目就不贴了,看书~~~

这个问题算是贪心算法中很经典的一道题目了。

按照书上所说,定义以下关系:

16_5

即:

16_6 (图有点丑~~~)

如果按照DP来做,可以找到以下关系:

16_7

不过,看看定理16.1(这个有必要自己仔细看看!)

它证明了为何这里可以用贪心。

Tanky Woo 标签:

(其实贪心这块和DP一样,很难说清楚,看多了,做多了,你就知道为何这个问题可以用DP,这个问题可以用贪心。。。)

下面贴出此题的代码:

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
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef struct Act{
	int s;   // start time
	int f;   // final time
}Act;
 
Act arr[100];
Act temp[100];
int n;
 
bool cmp(Act a, Act b)
{
	return a.f < b.f;
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	cout << "输入活动个数: ";
	cin >> n;
	cout << "输入" << n << "个活动的开始和结束时间:" << endl;
	for(int i=0; i<n; ++i)
		cin >> arr[i].s >> arr[i].f;
	sort(arr, arr+n, cmp);
	int k = 0;
 
 
	temp[k] = arr[0];
	for(int i=1; i<n; ++i)
		if(arr[i].s >= temp[k].f)
			temp[++k] = arr[i];
 
 
	cout << "选择的活动: " << endl;
	for(int i=0; i<=k; ++i)
		cout << temp[i].s << " " << temp[i].f << endl;
	return 0;
}

结果如图:

16_8

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — 22.第16章 贪心算法(2) 案例分析之活动选择问题》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注