下载文档原格式
贪⼼算法1、如何理解贪⼼算法贪⼼算法的思想是:每次都做出当前最优的选择，通过多步选择得出最终的最优解。
它适合解决上⼀步的选择不会影响下⼀步的选择的问题。
如果上⼀步的选择会影响下⼀步的选择，则使⽤贪⼼算法不⼀定能求出最优解。
1.1 能够使⽤贪⼼算法求解的问题举例问题：假如我们有⼀个能够容纳100Kg物品的袋⼦，可以装各种物品，不管物品的体积。
现在我们有5种⾖⼦，每种⾖⼦的总重量和总价值各不相同。
那如何往背包⾥⾯装这些⾖⼦，使得最后背包⾥物品的总价值最⼤呢？我们⼀眼就能知道这个问题的解法，先求出每种⾖⼦的单价，然后从单价⾼的⾖⼦开始装，装完单价⾼的，再去装次⾼的，直到袋⼦装满为⽌。
这个问题就适合⽤贪⼼算法来解，实际上上⾯的做法体现的就是贪⼼算法的思想（每次都做出当前最优的选择）。
这⾥第⼀步选择装单价最⾼的⾖⼦之后，不会影响第⼆步去选择装次⾼的⾖⼦的选择，同样第⼆步也不会影响第三步去选择单价排名第三的⾖⼦。
1.2 不能使⽤贪⼼算法来求解的问题举例问题：假如我们要在⼀个有权图中，从顶点S开始，找⼀条到顶点T的最短路径。
贪⼼算法的解决思路是，每次都选择⼀条根当前顶点相连的权最⼩的边（每次都做出当前最优的选择），直到找到顶点T。
按照这种思路，我们求出的最短路径是S->A->E->T,路径长度1+4+4=9;⽽实际的最短路径是S->B->D->T，路径长度2+2+2=6 。
为什么这⾥贪⼼算法得不到最优解呢？我们第⼀步从S->A和第⼀步从S->B，下⼀步⾯对的顶点和边是不⼀样的。
也就是我们前⾯的选择会影响后⾯的选择，所以得不出最优解。
⽐如：钱币找零'''假设现在市⾯上有 6 种不同⾯值的硬币，各硬币的⾯值分别为 5 分、1 ⾓、2 ⾓、5 ⾓、1 元、2 元，要找零 10.5 元，求出最少硬币的数量。
'''def getChange(coins, amount):coins.sort();# 从⾯值最⼤的硬币开始遍历i = len(coins)-1while i >= 0:if amount >= coins[i]:n = int(amount // coins[i])change = n * coins[i]amount -= changeprint (n, coins[i])i -= 1getChange([0.05,0.1,0.2,0.5,1.0,2.0], 10.5)再⽐如：使⽤贪⼼算法实现哈夫曼编码3.1 什么是哈夫曼编码哈夫曼编码是⼀种⼗分有效的编码⽅法，⼴泛应⽤于数据压缩中，其压缩率通常在20%~90%之间。
贪⼼算法（会场安排问题、区间选点）学习算法课程之后的第⼀次记录，渐渐的，程序设计考虑的因素增多，程序=数据结构+算法，这个等式让我深有体会。
从开始简单的C++编程，再到选择合适数据结构，现在需要更进⼀步，从算法层次上考虑程序执⾏的效率。
我对算法的理解是⽤更少的开销获得更优的执⾏效果。
分治法、动态规划在此之前没有记录下来，学到贪⼼算法的时候，觉得需要总结⼀下学过的东西，也能更好的理解。
动态规划的设计，要满⾜最优⼦结构性质和重叠⼦问题，采⽤⾃底向上的策略，计算出最优值，找到整体最优解。
这个过程有时候挺难的，主要在写出递归式，要⾃底向上填表。
贪⼼策略有点像动态规划，但在⼀些⽅⾯是不同的，有时候贪⼼算法的思想更容易想到。
它要满⾜⼦问题最优⽽得到整体最优？两个条件：最优⼦结构性质和贪⼼选择性质。
满⾜贪⼼选择性质⼀定满⾜最优⼦结构性质，⽽满⾜最优⼦结构性质不⼀定满⾜贪⼼选择性质，⽐如背包问题可以⽤贪⼼算法解决，⽽0-1背包问题只能⽤动态规划。
典型的贪⼼问题活动安排，有n个活动，给出开始时间和结束时间，要尽可能安排多的活动（时间互相不冲突）。
解决这个问题正确的贪⼼思想是以每个活动结束时间为⽐较变量，按结束时间升序排好活动次序，接着就进⾏⽐较选择。
⽽会场安排问题与活动⼜有些不同之处，下⾯是我的解题过程。
7-2 会场安排问题 (20 分)假设要在⾜够多的会场⾥安排⼀批活动，并希望使⽤尽可能少的会场。
设计⼀个有效的贪⼼算法进⾏安排。
（这个问题实际上是著名的图着⾊问题。
若将每⼀个活动作为图的⼀个顶点，不相容活动间⽤边相连。
使相邻顶点着有不同颜⾊的最⼩着⾊数，相应于要找的最⼩会场数。
）输⼊格式:第⼀⾏有 1 个正整数k，表⽰有 k个待安排的活动。
接下来的 k⾏中，每⾏有 2个正整数，分别表⽰ k个待安排的活动开始时间和结束时间。
时间以 0 点开始的分钟计。
输出格式:输出最少会场数。
输⼊样例:51 2312 2825 3527 8036 50输出样例:3#include<iostream>#include<algorithm>using namespace std;struct node {int begin;int end;int flag;//标记该活动是否被安排，0表⽰未安排，1表⽰已安排}t[10001];int cmp(const node &a,const node &b)//⽐较规则：以结束时间升序排列{return a.end<b.end;}int main(){int i,j,n;node temp;cin>>n;for(i=0;i<n;i++){cin>>t[i].begin>>t[i].end;t[i].flag=0;}sort(t,t+n,cmp);int sum=0;//总共需要的会场数量for(i=0;i<n;i++)//⽅法2{if(!t[i].flag)//找到未安排的活动，进⾏场地安排{sum++;int p=i;for(j=p+1;j<n;j++)//当前活动结束时间与下⼀个活动开始不相交，则安排到同⼀个会场{if(t[p].end<=t[j].begin&&!t[j].flag){p=j;t[j].flag=1;}}t[i].flag=1;}}cout<<sum;return0;}View Code贪⼼策略为：把尽可能多的时间互不冲突的活动安排到⼀个会场，若活动时间交叉，则在安排到另⼀个会场。
活动安排问题，对每项活动的按照结束时间非减序排列。
然后选第一个。
按照第一个的结束时间来看接下去怎么选，以此类推。
贪心选择性质的证明：
1.活动安排问题的一个最优解是以贪心选择开始。
即最优解包含第一个活动（叫做活动1）。
证明：假设有一个最优解叫做A。
它的活动也是以结束时间的非减序进行排列。
假设A中第一个活动叫做K。
如果K是我们的活动1，则A就是以活动1开始的。
如果K不是活动1.则把K从A中去掉，并加上活动1，而且活动1是相容的是因为活动1 的
结束时间最早。
所以证明了活动安排问题的一个最优解是以贪心选择开始。
最优子结构的证明：
把起始时间大于活动1的结束时间的活动去掉，A也可以把K去掉，这样子有一个递推的关系就是（总活动中）接下去那个与活动1相容的解必然可以相容在最优解（A-K）里面。
（因它又可以化为一个贪心选择的开始）所以每一步做出的贪心选择将使得原问题化为规模变小的相似的子问题。
C++贪⼼算法实现活动安排问题（实例代码）贪⼼算法贪⼼算法（⼜称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
具体代码如下所⽰：#include <cstdio>#include <iostream>#include <ctime>#include <windows.h>#include <algorithm>#include <fstream>using namespace std;struct activity{int no;int start;int finish;};bool cmp(const activity &x, const activity &y){return x.finish<y.finish;//从⼩到⼤排<，若要从⼤到⼩排则>}int greedySelector(int m,int solution[],struct activity activity[]){int number = 1;solution[0] = 1;int i,j = 0,counter = 1;for(i = 1;i < m ;i++){if(activity[i].start >=activity[j].finish){solution[i] = 1;j = i;counter++;}elsesolution[i] = 0;}cout << "The amount of activities is:"<<counter<<endl;cout << "The solution is:";for(i = 0 ;i < m ;i++){if (solution[i] == 1){cout << activity[i].no <<" ";}}return counter;}int main(void){LARGE_INTEGER nFreq;LARGE_INTEGER nBeginTime;LARGE_INTEGER nEndTime;ofstream fout;srand((unsigned int)time(NULL));int m,i,j,t;double cost;cout << "Please enter the number of times you want to run the program:";cin >> t;fout.open("activity.txt",ios::app);if(!fout){cerr<<"Can not open file 'activity.txt' "<<endl;return -1;}fout.setf(ios_base::fixed,ios_base::floatfield); //防⽌输出的数字使⽤科学计数法for (j = 0;j < t;j++){cout << "——————————————————The "<< j + 1 << "th test —————————————————"<<endl;m = 1 + rand()%100000;fout<<m<<",";int solution[m];activity activity[m];for( i = 0;i < m;i++){activity[i].no = i+1;activity[i].start = 1 + rand()%1000;while(1){activity[i].finish = 1 + rand()%10000;if(activity[i].finish > activity[i].start) break;}}QueryPerformanceFrequency(&nFreq);QueryPerformanceCounter(&nBeginTime);sort(activity,activity+m,cmp);greedySelector(m,solution,activity);QueryPerformanceCounter(&nEndTime);cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;fout << cost << endl;cout << "\nThe running time is:" << cost << " s" << endl;}fout.close();cout << endl << endl;cout << "Success!" << endl;return 0;}总结以上所述是⼩编给⼤家介绍的C++贪⼼算法实现活动安排问题，希望对⼤家有所帮助，如果⼤家有任何疑问请给我留⾔，⼩编会及时回复⼤家的。
0021算法笔记——【贪心算法】贪心算法与活动安排问题1、贪心算法(1)原理：在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
(2)特性：贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质。
1)贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素。
贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。
做了贪心选择后，原问题简化为规模更小的类似子问题。
然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
2)最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
(3)贪心算法与动态规划算法的差异:动态规划和贪心算法都是一种递推算法，均有最优子结构性质，通过局部最优解来推导全局最优解。
两者之间的区别在于：贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。
动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。
(4)基本思路：1)建立数学模型来描述问题。
2)把求解的问题分成若干个子问题。
3)对每一子问题求解，得到子问题的局部最优解。
4)把子问题的解局部最优解合成原来解问题的一个解。
2、活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。
该问题要求高效地安排一系列争用某一公共资源的活动。
贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
问题描述:设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi。
如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。
若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j 是相容的。
也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
求解思路：将活动按照结束时间进行从小到大排序。
然后用i代表第i个活动，s[i]代表第i个活动开始时间，f[i]代表第i个活动的结束时间。
按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。
事实上系统一次检查活动i是否与当前已选择的所有活动相容。
若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续下一活动与集合A中活动的相容性。
若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置。
下面给出求解活动安排问题的贪心算法，各活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非减序排列。
如果所给的活动未按此序排列，可以用O(nlogn)的时间重排。
具体代码如下：[cpp]view plain copy1.//4d1 活动安排问题贪心算法2.#include "stdafx.h"3.#include <iostream>ing namespace std;5.6.template<class Type>7.void GreedySelector(int n, Type s[], Type f[], bool A[]);8.9.const int N = 11;10.11.int main()12.{13.//下标从1开始,存储活动开始时间14.int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};15.16.//下标从1开始,存储活动结束时间17.int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};18.19.bool A[N+1];20.21.cout<<"各活动的开始时间,结束时间分别为："<<endl;22.for(int i=1;i<=N;i++)23.{24.cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;25.}26.GreedySelector(N,s,f,A);27.cout<<"最大相容活动子集为："<<endl;28.for(int i=1;i<=N;i++)29.{30.if(A[i]){31.cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;32.}33.}34.35.return0;36.}37.38.template<class Type>39.void GreedySelector(int n, Type s[], Type f[], bool A[])40.{41.A[1]=true;42.int j=1;//记录最近一次加入A中的活动43.44.for(int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容45.{46.if(s[i]>=f[j])47.{48.A[i]=true;49.j=i;50.}51.else52.{53.A[i]=false;54.}55.}56.}由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。
直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。
也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
算法greedySelector的效率极高。
当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。
如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。
例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：算法greedySelector 的计算过程如下图所示。
图中每行相应于算法的一次迭代。
阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。
贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。
这个结论可以用数学归纳法证明。
证明如下：设E=｛0，1，2，…，n-1｝为所给的活动集合。
由于E中活动安排安结束时间的非减序排列，所以活动0具有最早完成时间。
首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动0.设a是所给的活动安排问题的一个最优解，且a中活动也按结束时间非减序排列，a中的第一个活动是活动k。
如k=0，则a就是一个以贪心选择开始的最优解。
若k>0，则我们设b=a-｛k｝∪｛0｝。
由于end[0] ≤end[k],且a中活动是互为相容的，故b中的活动也是互为相容的。
又由于b中的活动个数与a中活动个数相同，且a是最优的，故b也是最优的。
也就是说b是一个以贪心选择活动0开始的最优活动安排。
因此，证明了总存在一个以贪心选择开始的最优活动安排方案，也就是算法具有贪心选择性质。
程序运行结果如下：。
