《算法导论》第16章-贪心算法 16.1-活动选择问题（含C++代码）

RECURSIVE-ACTIVITY-SELECTOR(s,f,k,n)
m = k+1
while m<=n and s[m]

• 1
• 2
• 3
• 4
• 5
• 6
• 7

迭代贪心算法

GREEDY-ACTIVITY-SELECTOR(s,f)
n = s.length
A={a1}	//将初值设置为只包含这个活动
k = 1	//设置为此活动下标
for m = 2 to n	//寻找sk中最早结束的活动
	if s[m]>=f[k]
		A=A∪{am}
		k=m
return A
1
2
3
4
5
6
7
8
9

C++代码（递归版本）

#include 
#include 
#include 
using namespace std;
vector<int> s = { 0,1,3,0,5,3,5,6,8,8,2,12 }, f = { 0,4,5,6,7,9,9,10,11,12,14,16 };
int RECURSIVE_ACTIVITY_SELECTOR(vector<int>& s, vector<int>& f, vector<int>& v_union, int k, int n)
{
	int m = k + 1;
	while (m <= n && s[m] < f[k]) {
		m++;
	}
	if (m <= n) {
		v_union.push_back(m);
		return RECURSIVE_ACTIVITY_SELECTOR(s, f, v_union,m, n);
	}
	else {
		return 0;
	}
}

int main()
{
	int n = 11;
	vector<int>v;
	RECURSIVE_ACTIVITY_SELECTOR(s, f, v,0, n);
	for (auto i : v) {
		cout << "a" << i << "  ";
	}
	return 0;
}
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

C++代码（迭代版本）

#include 
#include 
using namespace std;
vector<int> s = { 0,1,3,0,5,3,5,6,8,8,2,12 }, f = { 0,4,5,6,7,9,9,10,11,12,14,16 };

vector<int> Greedy_Activity_Selector(vector<int> const& s, vector<int> const& f) {
	int n = s.size() - 1;
	vector<int> A = { 1 };
	int  k = 1;
	for (int m = 2; m <= n; ++m) {
		if (s[m] >= f[k]) {
			A.push_back(m);
			k = m;
		}
	}
	return A;
}

int main() {
	vector<int> V = Greedy_Activity_Selector(s, f);
	for (auto& i : V) {
		cout << "a" << i << " ";
	}
	return 0;
}

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