贪心算法（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;
}