贪心算法学习
贪心算法
贪心算法的基本要素
- 最优子元素
- 贪心选择性质
贪心算法的设计要素
- 适用于组合优化问题
- 求解过程是多步判断的过程，最终的判断序列对应于问题的最优解
- 判断依据某种“短视的”贪心选择性质，性质的好坏决定了算法的成败
- 贪心法必须进行严格的证明
贪心算法的应用
贪心算法在许多优化算法中有广泛运用：
- 最小生成树
Prime算法 Kruskal算法- 单源最短路径的
Dijkstra算法 - 数据压缩的
Huffman算法等
由一个简单的例子来介绍：
活动安排问题
【问题描述】
设有 \(n\) 个活动的集合 \(E={1,2,…,n}\)，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 \(i\) 都有一个要求使用该资源的起始时间 \(S_i\) 和一个结束时间 \(F_i\)，且 \(S_i
如果选择了活动 \(i\)，则它在时间区间 \([S_i,F_i)\) 内占用资源。若区间 \([S_i,F_i)\) 与区间 \([S_j,F_j)\) 不相交，则称活动 \(i\) 与活动 \(j\) 是相容的。也就是说，当 \(F_i≤S_j\) 或 \(F_j ≤ S_i\)时，活动 \(i\) 与活动 \(j\) 相容。选择出由互相兼容的活动组成的最大集合。
【输入格式】
第一行一个整数 \(n\)；
接下来的 \(n\) 行，每行两个整数 \(s_i\) 和 \(f_i\)。
【输出格式】
输出互相兼容的最大活动个数。
【输入样例】
4
1 3
4 6
2 5
1 7
【输出样例】
2
定义声明变量：
st[i]来存储是否选中了活动 \(i\)Act[i].start用来存储第 \(i\) 个活动的开始时间Act[i].end用来存储第 \(i\) 个活动的结束时间- \(j\) 表示最近一次加入选中的活动
cnt存储选中活动的数目
解题步骤
-
步骤一：
- 用结构体数组来存储活动起始时间，优点是方便按照活动结束时间对活动进行排序。
struct Activity { int start ; int end ; }Act[1005]; -
步骤二：
- 对活动按照终止时间从小到大进行排序
bool cmp(Activity a,Activity b){ return a.end -
步骤三
- 决定是否选择下一个活动,当下一个活动的开始时间小于等于选中的最晚时间时，将这下一个活动选中，并更新
j
for(int i = 2 ; i < n ; i ++){ if(Act[i].start >= Act[j].end){ cnt ++ ; st[j] = true ; j = i ; } } - 决定是否选择下一个活动,当下一个活动的开始时间小于等于选中的最晚时间时，将这下一个活动选中，并更新
源码
#include
using namespace std;
const int N = 1e5+10 ;
bool st[N] ;
struct Activity
{
int start ;
int end ;
}Act[1005];
bool cmp(Activity a,Activity b){
return a.end> n ;
for(int i = 1 ; i <= n ; i ++){
cin >> Act[i].start >> Act[i].end ;
}
sort(Act+1,Act+1+n,cmp);
int j = 1 ;
st[1] = true ;
int cnt = 1 ;
for(int i = 2 ; i < n ; i ++){
if(Act[i].start >= Act[j].end){
cnt ++ ;
st[j] = true ;
j = i ;
}
}
cout << cnt ;
return 0;
}
最小延迟调度
【问题描述】
给定等待服务的客户集合\(A=\){\(1,2，… , n\)}, 预计对客户 \(i\) 的服务时间是 \(t_i\) , 该客户希望的完成时间是 \(d_i\) , 即\(T=
【输入形式】客户数 \(n\)，各客户服务时间及期望完成时间
【输出形式】最小延迟时间调度安排及延迟时间
【样例输入】
5
5 8 4 10 3
10 12 15 11 20
【样例输出】
1 4 2 3 5
12
求最大延迟达到的最小调度就是求 \(f\) 使得
\[\min_{f}{\max_{i\in A}{(f(i)+t_i-d_i))}} \]样例解释
- 客户集合：A = {1 , 2 , 3 , 4 , 5}
- 服务时间集合：T = {5 , 8 , 4 , 10 , 3}
- 截止时间：D = {10 , 12 , 15 , 11 , 20}
假设调度安排按照顺序
不难得出\(f_1(1) = 0 ,f_1(2) = 5,f_1(3)=13,f_1(4) = 17,f_1(5) = 27\)
各个任务延迟：\(0,1,2,16,10\)
最大延迟为 ：\(16\)
我们的任务就是在所有的调度情况下找到最大延迟最小的那种情况，并输出其最大延迟与分配调度。
定义声明变量：
now来存储选择某方案情况下，服务时间之和。 在\(now\) 的更新过程中，也是对最大延迟时间的更新。ans用来存储最大延迟时间
解题步骤
-
步骤一：
- 用结构体数组来存储活动起始时间，优点是方便按照活动结束时间对活动进行排序。
struct node{ int first,second; int id;// 这里的id代表客户的num }arr[maxn]; -
步骤二：
- 对活动按照终止时间从小到大进行排序
bool cmp(node a,node b){ return a.second<=b.second; } sort(arr+1,arr+n+1,cmp); -
步骤三：
- 对每个服务时间和截止时间进行判定，\(now\) 来累加总的服务时间。若\(now\) 大于截止时间就更新 \(ans\) ，经过\(n\) 次迭代,\(ans\) 被更新为\(n\)个延迟中最大的那个延迟。
for(int i=1;i<=n;i++){ cout<
源码
#include
using namespace std;
const int maxn = 1e6+10;
struct node{
int first,second;
int id;
}arr[maxn];
bool cmp(node a,node b){
return a.second<=b.second;
}
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i].first;
arr[i].id=i;
}
for(int i=1;i<=n;i++) cin>>arr[i].second;
sort(arr+1,arr+n+1,cmp);
int now=0,ans=0;
for(int i=1;i<=n;i++){
cout<arr[i].second) ans=max(ans,now-arr[i].second);
}cout<