贪心算法（Greedy Algorithm）

一、简介

算法>贪心算法是一种在每一步选择中都做出当前最优解的算法，以期通过这些局部最优解，最终得到全局最优解。它的核心思想是贪心选择性质，即每一步都选择能带来最优解的那个选项，而不考虑后续步骤的影响。

步骤：

1、建立贪心选择标准：确定可以用来判断当前局部最优解的标准

2、验证贪心选择性质：确保在局部最优的条件下，整体的解也是最优的

3、问题缩小：将问题分解为子问题，并应用贪心策略qiuj

4、构建解：根据每一步的选择构造最终的解

二、动态规划算法和算法>贪心算法的区别

三、算法优势/适用场景

1、活动选择问题：选择能够参加最多活动的时间安排。

2、最小生成树问题：Kruskal和Prim算法都基于贪心思想。

3、单源最短路径问题：Dijkstra算法也是一种算法>贪心算法。

4、哈夫曼编码

四、例题（C++，随缘更新）

1、会场安排问题

题目来源：计算机算法设计与分析（第五版）王晓东

问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法>贪心算法进行安排。对于给定的k个待安排的活动，计算使用最少会场的时间表。

数据输入：第1行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动的开始时间和结束时间。时间以0点开始的分钟计。

结果输出：将计算的最少会场数输出。

输入示例：输出示例：

5 3

1 23

12 28

25 35

27 80

36 50

问题分析：这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相当于要找的最小会场数。

算法>贪心算法思想：先将活动按开始时间排序，然后遍历每一个活动，对于一个活动，再遍历每一个会场，如果这个活动在这个会场的最后一个活动结束时间之后，就说明可以在这个会场安排本活动，如果遍历完所有会场都无法安排那么就新增会场。

样例分析：示例的活动已经是按照开始时间排好序的了，那么下面依次遍历每个活动，首先对于第一个活动，目前还没有分配会场，所以肯定要新增一个会场，那么这个会场的结束时间就是这个活动的结束时间，为23。然后对于第二个活动，开始时间为12<23说明无法安排在第一个会场，现在新增第二个会场，结束时间为28。对于第三个活动，开始时间为25>23，则可以安排在第一个会场，第一个会场结束时间更新为35。对于第四个活动，开始时间为27<35，27<28，所以无法安排在前两个会场，那么此时新增第三个会场，结束时间为80。对于第五个活动，开始时间为36>35，可以安排在第一个会场，分配完毕，一共需要三个会场。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//活动的结构体 
struct activity{int start;//开始时间 int end;//结束时间 
};bool cmp(activity a, activity b)
{if(a.start!=b.start){return a.start < b.start;}return a.end < b.end;
}
int minRoom(vector<activity>& activities)
{//按活动开始时间排序 sort(activities.begin(), activities.end(), cmp);//记录每个会场的结束时间vector<int> endtime;//开始处理每一个活动 for(int i = 0; i < activities.size(); i++){bool flag = false;//标记是否分配成功for(int j = 0; j < endtime.size(); j++){//活动的开始时间在会场所有活动结束时间以后，就说明可以再安排活动 if(activities[i].start > endtime[j]){//更新会场结束时间 endtime[j] = activities[i].end;flag = true;break;}}//如果没找到，新增一个会场if(!flag){endtime.push_back(activities[i].end);} }return endtime.size();
}int main(int argc, char** argv) {int n;cin >> n;vector<activity> activities(n);//输入开始时间和结束时间 for(int i=0;i<n;++i){cin >> activities[i].start >> activities[i].end;}//计算int	result = minRoom(activities); //结果输出cout << result << endl; return 0;
}

2、最优合并问题

题目来源：计算机算法设计与分析（第五版）王晓东

问题描述:给定k个排好序的序列s1,s2.…,sk，用2路合并算法将这大个字列合并成一个序列。假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并序，使所需的总比较次数最多。

数据输入：第1行有1个正整数k，表示有k个待合并序列。接下来的1行中，有k个正整数，表示k个待合并序列的长度。

结果输出：输出最多比较次数和最少比较次数

输入示例：输出示例：

4 78 52

5 12 11 2

问题分析：该问题类似于哈夫曼编码的思想，我们通过算法>贪心算法可以找到最优合并顺序，使得比较次数最少，为了得到最多比较次数，我们则需要采用反向的贪心策略。

贪心策略：对于最少比较次数即每次合并序列最短的两个序列；对于最多比较次数即合并最长的两个序列。

样例分析：

（1）最少比较次数

从小到大排序：2,5,11,12，将2和5合并，得到新的序列7，次数为6

从小到大排序：7,11,12，将7和11合并，得到新的序列18，次数为17

从小到大排序：12,18，将12和18合并，得到新的序列30，次数为29

最少次数min = 6+17+29 = 52

（2）最多比较次数

从大到小排序：12,11,5,2，将12和11合并，得到新的序列23，次数为22

从大到小排序：23,5,2，将23和5合并，得到新的序列28，次数为27

从大到小排序：28,2，将28和2合并，得到新的序列30，次数为29

最多次数max = 22+27+29 = 78

代码实现：

#include <iostream>
#include <algorithm>using namespace std;//从大到小排序 
bool cmp(int a, int b)
{return a > b;} // 计算最少比较次数
int minnum(int lengths[], int k) {int min = 0;for(int i=0; i<k-1; ++i) {sort(lengths+i,lengths+k);//从小到大排序 ，只需排序还未进行合并的序列 lengths[i+1] = lengths[i] + lengths[i+1];//把合并后的序列长度赋值给a[i+1] min+=lengths[i+1]-1;//合并次数为m+n-1，即合并后的长度-1 }return min;
}// 计算最多比较次数
int maxnum(int lengths[], int k) {int max = 0;for(int i=0; i<k-1; ++i) {sort(lengths+i,lengths+k,cmp);//从大到小排序 ，只需排序还未进行合并的序列 lengths[i+1] = lengths[i] + lengths[i+1];//把合并后的序列长度赋值给a[i+1] max+=lengths[i+1]-1;//合并次数为m+n-1，即合并后的长度-1 }return max;
}int main() {int k;cin >> k;//复制一份数据，因为在计算max时，数组中的值会被更改 int lengths[k], len[k];for (int i = 0; i < k; i++) {cin >> lengths[i];len[i] = lengths[i];}cout << maxnum(lengths,k) << " "  << minnum(len,k) << endl;return 0;
}