avarice
贪心
定义
- 在对问题求解时，总是做出在当前看来是最好的选择。也就是说不从整体最优上考虑，而是在某种意义上求局部最优解，每次局部都是最优解则得到整体最优解
注意
- 不是对所有问题都能得到最优解，关键是贪心策略的选择
- 贪心算法的前提：局部最优解一定能导致全局最优解，且每次选择不会影响后续的选择
贪心的过程
建立模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解；
例题讲解
活动选择
原题链接
answer
贪心策略：优先选择结束时间最早的活动。这样可以为后续活动留出更多的时间。
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
| #include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
struct Activity{
int Start_Time;
int Stop_Time;
};
bool compare(Activity a1,Activity a2){
return a1.Stop_Time<a2.Stop_Time;
}
int main(){
int n,ans=0;
cin >> n;
vector<Activity> activities(n);
for(int i =0;i<n;i++){
cin>>activities[i].Start_Time>> activities[i].Stop_Time;
}
sort(activities.begin(),activities.end(),compare);
int LastSelect = activities[0].Stop_Time;
ans++;
for(int i=1;i<n;i++){
if(LastSelect <= activities[i].Start_Time){
LastSelect = activities[i].Stop_Time;
ans++;
}
}
cout<<ans<<endl;
return 0;
}
|