五大常用算法之贪心算法
时间: 2023-07-04 10:03:31 浏览: 77
贪心算法(Greedy Algorithm)是一种在每一步选择中都采取当前状态下最优的选择,从而希望最终导致全局最优的算法。贪心算法通常有以下特点:
1. 贪心选择性质:每一步都采取最优的选择,即局部最优解。
2. 最优子结构性质:原问题的最优解包含子问题的最优解。
3. 无后效性:每一步的决策只与当前状态有关,与之前的决策无关。
贪心算法可以用来求解一些最优化问题,如最小生成树、背包问题、活动选择问题等。
以活动选择问题为例,假设有n个活动,每个活动有一个开始时间s和结束时间f,多个活动可能在同一时间段内进行,但是同一时间只能进行一个活动。如何选择活动,使得能够安排的活动数量最多?
贪心算法的思路是:按照结束时间从早到晚排序,每次选择结束时间最早的活动,且不与已经选择的活动时间冲突。这是因为选择结束时间最早的活动,可以给后面留下更多的时间选择其他活动,从而使得总的安排活动数量最多。
参考代码如下:
```
#include <iostream>
#include <algorithm>
using namespace std;
struct Activity {
int start, finish;
};
bool compare(Activity s1, Activity s2) {
return (s1.finish < s2.finish);
}
void printMaxActivities(Activity arr[], int n) {
sort(arr, arr+n, compare);
cout << "Selected activities:\n";
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << "), ";
for (int j = 1; j < n; j++) {
if (arr[j].start >= arr[i].finish) {
cout << "(" << arr[j].start << ", " << arr[j].finish << "), ";
i = j;
}
}
}
int main() {
Activity arr[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxActivities(arr, n);
return 0;
}
```
输出结果为:
```
Selected activities:
(1, 2), (3, 4), (5, 7), (8, 9),
```
可以看到,按照贪心算法的思路,选择了4个活动,使得能够安排的活动数量最多。