贪心算法 贪心算法总是作出在当前看来最好的选择。 贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 这两种算法都是选择性算法，就是从一个候选集合中选择适当的元素加入解集合。 贪心算法和动态规划算法的比较 贪心算法的选择策略即贪心选择策略，通过对候选解按照一定的规则进行排序，然后就可以按照这个排好的顺序进行选择了，选择过程中仅需确定当前元素是否要选取，与后面的元素是什么没有关系。 动态规划的选择策略是试探性的，每一步要试探所有的可行解并将结果保存起来，最后通过回溯的方法确定最优解，其试探策略称为决策过程。 这两种算法都是选择性算法，就是从一个候选集合中选择适当的元素加入解集合。 贪心算法的选择策略即贪心选择策略，通过对候选解按照一定的规则进行排序，然后就可以按照这个排好的顺序进行选择了，选择过程中仅需确定当前元素是否要选取，与后面的元素是什么没有关系。 动态规划的选择策略是试探性的，每一步要试探所有的可行解并将结果保存起来，最后通过回溯的方法确定最优解，其试探策略称为决策过程。 整体最优与局部最优
前有面值分别为1角1分，5分，1分的硬币，请给出找1角5分钱的 贪心（5枚）： 15-11=4 4-41=0 最佳（3枚） 35 5.1 活动安排问题 活动安排问题的贪心特性（贪心的体现：最多的活动）。 如何在有限的时间内安排更多的活动（贪心策略）？ 需要先安排结束时间早的活动（剩余时间多） 。 因此，需要根据活动的结束时间对活动进行排序 在排序的基础上，依次来寻找相容的活动
数据结构
struct action{ int s; //起始时间 int f; //结束时间 int index; //活动的编号 };活动的集合E记为数组： action a[1000];
void Greedy(vector<Action> &v,int n){ v[0].select=1; int select=0; for(int i=1;i<n;i++) { if(v[i].gets()>=v[select].gete()){ v[i].select=1; select=i; } } cout<<"可以安排如下的活动："<<endl; for(i=0;i<n;i++) if(v[i].select) v[i].display(); }贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解? 下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。
背包问题
double knapsack(int n, bag a[], double c){ double cleft = c; //背包的剩余容量 int i = 0; double b = 0; //背包内物品的总价值获得的价值 //当背包还能完全装入物品i while(i<n && a[i].w<cleft) { cleft -= a[i].w; b += a[i].v; i++; } //装满背包的剩余空间 if (i<n) b += 1.0*a[i].v*cleft/a[i].w; return b; }最优装载问题 有一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船（件数最多）。 该问题的形式化描述为：
其中xi∈{0，1}，1≤i≤n。 代码描述
template<class Type> void Loading(int x[], Type w[], Type c, int n){ int *t = new int [n+1]; Sort(w, t, n);//t 存储的是按重量排好序的集装箱的序号 for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) { x[t[i]] = 1; c - = w[t[i]]; } }单源最短路径 Dijkstra算法是解单源最短路径问题的一个贪心算法。 设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源。 设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。 Dijkstra算法每次从V - S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。(贪心策略) 一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。 最短路问题的贪心特性 Kruskal算法 设G=(V,E)是连通带权图，V＝{v1，v2 ，…，vn}。 Kruskal算法构造G的最小生成树的基本思想： 将G的n个顶点看成n个孤立的连通分量，将所有的边按权从小到大排序。 从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分量： 当查看到第i条边（u，v）时，如果端点u和v分别是当前两个不同的连通分量T1和T2中的顶点时，就用边(u，v)将T1和T2连接成一个连通分量，然后继续查看第i＋1条边； 如果端点u和v在当前的同一个连通分量中，就直接再查看第i＋1条边。 这个过程一直进行到只剩下一个连通分量时为止，该连通分量就是G的一棵最小生成树。
当查看到第i条边（u，v）时，如果端点u和v分别是当前两个不同的连通分量T1和T2中的顶点时，就用边(u，v)将T1和T2连接成一个连通分量，然后继续查看第i＋1条边； 如果端点u和v在当前的同一个连通分量中，直接查看第i＋1条边。
**Kruskal算法思想 **
初始化：U=V； TE={ }；循环直到T中的连通分量个数为1 2.1 在E中寻找最短边(u，v); 2.2 如果顶点u、v位于T的两个不同连通分量，则 2.2.1 将边(u，v)并入TE； 2.2.2 将这两个连通分量合为一个； 2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取； int cmp(const point &a,const point &b) { //sort()自定义的比较函数 if (a.v < b.v) return 1; else return 0; } int main(){ cin >> n; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { cin >> x; m++; a[m].x = i; a[m].y = j; a[m].v = x; } for (i = 1; i <= n; i++) fat[i] = i; sort(a+1,a+m+1,cmp);并查集的基本思想 1、什么叫并查集 并查集（union-find set）是一抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系， 当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。 删数问题 大整数的表示的问题 输入：字符串 存储： 整数数组（或字符数组） 贪心策略： 表面上看，删除最大的数。 但是 对于14385 ，删除一位 按照删除最大数的策略，1435 如果删除4： 1385（<1435） 因此，贪心策略为： 寻找最近下降点
#include <iostream> #include <string> using namespace std; int main(){ string a; //n位数a int k; //删除数字的个数 cin>>a>>k; if (k >= a.size()) a.erase(); //如果k≥n，所有数字均被删除 else while(k > 0){ //寻找最近下降点，逐个删除 int i; for (i=0; (i<a.size()-1) && (a[i] <= a[i+1]); ++i); a.erase(i, 1);//删除xi k--; } while(a.size() > 1 && a[0] == '0') //删除前导数字0 a.erase(0, 1); cout<<a<<endl; }汽车加油问题 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。要求： 输入：第一行有2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。 输出：输出编程计算出的最少加油次数。如果无法到达目的地，则输出”No Solution”。 加油问题的贪心特性 加一次油，跑最远的距离 到达加油站之后，看看剩余的油能否跑到下一个加油站； 能，则不用加油 否则，加油 代码
#include <iostream> using namespace std; int main(){ int n,k,i; int *station; cout<<"请输入加满一箱油的最大行驶路程和加油站的个数："; cin>>n>>k; station=new int[k+1]; cout<<"请输入相邻的两个加油站之间的距离："; for(i=0;i<=k;i++) cin>>station[i]; int s=0,number=0;//number记录加油的次数 s=station[0];//加满油后希望的行驶距离 for(i=1;i<=k;i++){ //i代表加油站编号 。1~7.代表将要到大的加油站 if(s>n) {cout<<“No solutin!!”; break; }//判断能否到达i加油站 else{//能到达加油站i s=s+station[i]; //到下一加油i+1站希望的 行使的距离 if(s>n){ //希望距离>n number++;//加油 s=station[i];//到下一加油站的距离 cout<<"在第"<<i<<" 个加油站加油"<<endl; } } } cout<<number<<endl; return 0; }多处最优服务次序问题 算法分析： 只有一个资源，2个顾客，需要服务时间分别是10，1. 要使等待时间（包括服务所需要的时间）最短，按照什么顺序处理？ 两个资源，三个客户，需要服务时间分别是1，10，5 要使等待时间最短，按照什么顺序处理？
由此，任务的解决具有什么特点。 设计贪心策略如下： 对服务时间最短的顾客先服务的贪心选择策略。 首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T’。 新问题和原问题相同，只是问题规模由n减小为n - 1。 基于此种选择策略，对新问题T’，在n-1个顾客中选择服务时间最短的先进行服务，如此进行下去，直至所有服务都完成为止。
//顾客等待的队列为client，提供服务的窗口s个 double greedy(vector<int> client, int s){ vector<int> service(s, 0); //服务窗口的单个顾客等待时间 vector<int> sum(s, 0); //服务窗口顾客等待时间的总和 int n = client.size(); //顾客的数量 sort(client.begin(), client.end()); //按顾客的服务时间升序排序 int i=0; //顾客的指针 int j=0; //窗口的指针 while(i < n){ service[j] += client[i]; sum[j] += service[j]; ++i, ++j; if(j == s) j = 0; } double t=0; //计算所有窗口服务时间的总和 for(i=0; i<s; ++i) t += sum[i]; t /= n; return t; }导弹拦截问题
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。 【输入格式】 n颗依次飞来的高度（1≤n≤1000）. 【输出格式】 要拦截所有导弹最小配备的系统数k。 【输入样例】missile.in 389 207 155 300 299 170 158 65 【输出样例】missile.out 2
k=1;l[k]=导弹1的高度; for (i=2;i<=n;++i) { p=0; for (j=1;j<=k;++j) //考察每一套拦截系统 if (l[j]>=导弹i的高度) {//i贪心策略，寻找最低高度最小的拦截系统 if (p==0) p=j; else if (l[j]<l[p]) p=j; } if (p==0) { ++k;l[k]=导弹i的高度; } //增加一套新系统 else l[p]=导弹i的高度; //贪心,更新第p套系统的最低高度 } 输出应配备的最少系统数K。**均分纸牌（NOIP2002） ** 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。 移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
代码
cin>>n; ave=0;step=0; for (i=1;i<=n;++i) { cin>>a[i]; ave+=a[i]; //读入各堆牌张数，求总张数ave } ave/=n; //求牌的平均张数ave for (i=1;i<=n;++i) a[i]-=ave; //每堆牌的张数减去平均数 i=1;j=n; while (a[i]==0&&i<n) ++i; //过滤左边的0 while (a[j]==0&&j>1) --j; //过滤右边的0 while (i<j) { a[i+1]+=a[i]; //将第i堆牌移到第i+1堆中去 a[i]=0; //第i堆牌移走后变为0 ++step; //移牌步数计数 ++i; //对下一堆牌进行循环操作 while (a[i]==0&&i<j) ++i; //过滤移牌过程中产生的0 } cout<<step<<endl;有n个人要过一条河，每个人过河都需要一个时间，有一艘船，每次过河只能最多装两个人。两个人划船过河所需的时间都取决于过河时间长的那个人。比如，A，B两人过河所需时间分别为a，b，那么，他们成一条船过河所需的时间为：max{a，b}。现在让你安排一个过河方案，让所有人用最短的时间全部过河。 输入：第一行给出人的数量 //接下来的1行给出每个人的速度 //4 //1 2 5 10 输出 最短时间 17 分析 设其中四人为a、b、c、d，并且所需时间a<b<c<d 那么，现在想让c、d过河，然后再让船回到过河前的位置，准备好继续送其他的人过河。有两种运载方式： 1.过河顺序为：ac、a、ad、a 时间消耗：t 1 =2a+c+d 2.过河顺序为：ab、a(b)、cd、b(a) 时间消耗：t 2 =a+2b+d t 1 −t 2 =a+c−2b 选择两种方案的哪一种，和a+c−2b 的值有关。 代码
#include<iostream> #include<algorithm> using namespace std; int x[1100]; int min(int a, int b ){ if(a>=b)return b; return a; } int main(){ int N; cin>>N; for(int i=1;i<=N;++i) cin>>x[i]; sort(x+1,x+N+1);ZOJ1029-Moving Tables 这层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。 由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制定计划提高搬运效率。 经理制定如下计划：一张办公桌从一个房间移到另一个房间最多用十分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公桌 ACM公司搬运办公桌的贪心算法实现
int i, j; int move[200]; int N; //搬运次数 int from, to; //每次搬运的起点和终点 scanf("%d", &N); memset(move, 0, sizeof(move)); for(i = 0; i < N; i++){ scanf("%d%d", &from, &to); from = (from - 1)/2; //将房间号映射为走廊号。走廊数组下标从0开始 to = (to - 1)/2; //确保from<to，C++使用：swap(from, to) if(from > to) { int temp = from; from = to; to = temp; } //占用走廊情况 for(j = from; j <= to; j++) move[j]++; } **钓鱼问题** 两个湖，1小时（=60分钟） 第一个湖：可以钓到的鱼的数量为 10+8+6+4+2=30， 耗时5*5=25分钟 第二个湖：钓鱼数量为： 1. 总的数量为31 条。 时间还有空余，但已经无鱼可钓。 因此钓鱼方式可以有 25+35 ，30+30……45+5等多种方案 根据规则 在两个湖的停留时间分别是 45, 5 ```cpp //从湖1起到湖pos止，花费时间time（不含路程）的钓鱼计划 void greedy(int pos, int time) { if (time <= 0) return; //时间已经用完 int i, j; int fish[MAXN]; //每个湖能钓到鱼的数量 int p[MAXN]; int t = 0; for (i = 1; i <= pos; ++i) fish[i] = f[i]; memset(p, 0, sizeof(p)); …… } //在时间time内，选择鱼最多的湖钓鱼；如果鱼都没有了，就把时间放在湖1上 for (i = 0; i < time; ++i){ int max = 0; //鱼最多的湖中，鱼的数量 int id = -1; //鱼最多的湖的编号 //查找鱼最多的湖中，鱼的数量和湖的编号 for (j = 1; j <= pos; ++j) if (fish[j] > max){ max = fish[j]; id = j; } if (id != -1) //找到了，进行钓鱼处理 { ++p[id]; fish[id] -= d[id]; t += max; } //没有找到（从湖1起到湖pos全部钓完了），就把时间放在湖1上 else ++p[1]; }