【背景知识】
【贪心算法】顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体 最优考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法 得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解， 但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一 些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
【贪心算法的基本要素】
对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性质和最优子结构性质。
【贪心选择性质】
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
【最优子结构性质】
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
模型一：最基本的模型
- 题目描述：
-
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
- 输入：
-
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
- 输出：
-
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
- 样例输入：
-
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1
- 样例输出：
-
13.333 31.500
1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 struct Trade 5 { 6 int j,f; 7 double percent; 8 }mouse[3001]; 9 bool cmp(Trade a,Trade b) 10 { 11 return a.percent>b.percent; 12 } 13 int main() 14 { 15 int n,m; 16 while(scanf("%d%d",&m,&n)!=EOF&&(n!=-1||m!=-1)) 17 { 18 int i; 19 20 for(i=0;i<n;i++) 21 { 22 scanf("%d%d",&mouse[i].j,&mouse[i].f); 23 mouse[i].percent=(double)mouse[i].j/mouse[i].f; 24 } 25 sort(mouse,mouse+n,cmp); 26 double sum=0; 27 for(i=0;i<n;i++) 28 { 29 if(m>mouse[i].f) 30 { 31 sum+=mouse[i].j; 32 m-=mouse[i].f; 33 } 34 else 35 //break; 36 { 37 sum+=mouse[i].percent*m; 38 m=0; 39 break; 40 } 41 42 43 } 44 45 printf("%.3lf ",sum); 46 47 } 48 return 0; 49 }
这是个最基本的贪心算法模型，但是包含了基本的思路模式：首先分析系统的特性，找到基本的最小模型。此题中老鼠要用有限的猫粮换取自己的食物，不同的仓库不一样，先根据性价比进行排序。（贪心算法都有排序，不同的模型的排序对象不同）然后从性价比最高到最低开始遍历，如果手上的猫粮够，就换取性价比最高的食物，如果不够，就换取相应的比例，一直到猫粮耗尽。最后得到的就是能获得的最多猫粮。
模型二：暑假不AC
Problem Description
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）Input输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。Output对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。Sample Input12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0Sample Output51、若A是E的最优解，那么E-A 也是问题的最优解，在余下的问题里，继续拿最早结束的；
2、拿可以开始的最早结束。(所以要按结束时间排序一次，然后把可以开始的选择上，然后继续向后推)
把输入的数据按照电视节目结束的时间从小到大进行排序（排序的目的是使取的结束时间都比剩下的结束时间要早 这样才能看更多的节目） 对应的开始时间也进行了排序
然后从第一个结束时间开始 寻找下一个比他晚的开始时间 如果找到了 节目数就加1（初始的节目数为1 因为选了第一个结束时间就是一个节目了）#include<stdio.h> #include<iostream> #include<vector> #include<algorithm> using namespace std; struct SE { int Ti_s; int Ti_e; }; bool cmp(SE a, SE b) { if(a.Ti_e < b.Ti_e) return true; else return false; } int main() { int n; while(scanf("%d",&n)!=EOF && n!=0) { vector<SE>v; for(int i=0;i<n;i++) { SE se; scanf("%d %d",&se.Ti_s,&se.Ti_e); v.push_back(se); } sort(v.begin(),v.end(),cmp);//对数据以Ti_e进行升序排序 int flag=0,count=1; for(int j=1;j<n;j++) { if(v[j].Ti_s>=v[flag].Ti_e) { count++; flag=j;//不断向前推进，记录要对比的最早时刻 } } printf("%d ",count); } return 0; }
模型三：零件加工问题：
【问题描述】有个国有中型企业，接到一批需要加工零件的订单，员工们非常高兴，可是高兴之后却发现问题了，原来这家企业能够加工这批零件的机床有限，如 果仅仅为了这批加工任务而新添机床的话，那么既不合算也不必要，因为加工完这批零件后很可能这些机床又要闲置起来，所以大批量购买肯定不行，但这批订单又必须要完成，那么这么办呢？很想请你帮忙设计一个安排加工任务，使得完成这批订单所需要使用的机器数量最少。假定对于待加工的第个零件，给你两个非负整数，，其中表示加工开始的时间，其中表示加工结束的时间，由于受到客观条件的制约，开始和结束的时间限制必须要遵守。当然在某个时刻一台机器只能加工一个零件。
【输入说明】本问题有多组测试数据，对于每组测试数据，输入的第一行是需要加工的零件个数，接着是行，其中，如上所述。
【输出说明】输出只有一行，就是完成加工任务所需要的最少机床数。
【Sample Input】
7
[6，9]
[1，4]
[2，5]
[3，7]
[4，7]
[1，3]
[7，8]
【Sample Output】
3
a) 预备（排序）：按照零件加工的起始时间和结束时间进行排序，注意排序的主关键字是起始时间，当起始时间相同时才要按照结束结束时间排序。
b) 第一步：如果没有零件需要加工，那么当然需要的机床数是零。
c) 第二步：如果有零件需要加工，那么至少需要一台机床。
d) 第三步：如果在现有的机床上能够加工新的零件，那么就不需要增加新的机床，如果安排不下，才要增加一台机床。
e) 第四步：重复第三步，直到所有的零件都有机床来加工。
【算法优化】
算法的第一步、第二步和第四步是没什么可优化的，下面我们来分析一下算法的第三步。
如果能安排的下，就是指“零件和机床不矛盾”，现在机床可不是一台，有很多台，所以只要找到一台机床能安排下就可以了，如果所有的机床都找遍了，还是安排不下，那么只有增加机床。设当前已经有台机床，分别是，新的待加工的零件是第个零件，这样我们可以描述“查找可以在台机床里的哪台能安排的算法”了。
#include<iostream> #include<algorithm> using namespace std; #define MAX 1001 structstuTime { intnSi; intnEi; }; stuTimestuPart[MAX],stuMachine[MAX]; void vInit(); void vInput(intnP); boolbCmp(conststuTime&stuA,conststuTime&stuB); void vSort(intnP); intnGetMachine(intnP); void vOut(intnM); intnFind(intnP,intnM); int main() { intnPart; intnMachine; while(1==scanf("%d",&nPart)) { vInit(); vInput(nPart); vSort(nPart); nMachine=nGetMachine(nPart); vOut(nMachine); } return 0; } void vInit() { memset(stuPart,0,sizeof(stuPart)); memset(stuMachine,0,sizeof(stuMachine)); } void vInput(intnP) { int i; for(i=1;i<=nP;i++) { scanf(" [%d,%d]",&stuPart[i].nSi,&stuPart[i].nEi); //scanf("[%d,%d]",&stuPart[i].nSi,&stuPart[i].nEi);这里两行只差一个空格，有差别的空格是有意义的！ } } boolbCmp(conststuTime&stuA,conststuTime&stuB) { if(stuA.nSi==stuB.nSi) return (stuA.nEi<stuB.nEi); return (stuA.nSi<stuB.nSi); } void vSort(intnP) { sort(&stuPart[1],&stuPart[nP+1],bCmp); } intnGetMachine(intnP) { intnRet; int i; intnTemp; nRet=0; for(i=1;i<=nP;i++) { nTemp=nFind(i,nRet); if(nTemp<=nRet) { stuMachine[nTemp].nEi=stuPart[i].nEi; } else { nRet++; stuMachine[nRet].nSi=stuPart[i].nSi; stuMachine[nRet].nEi=stuPart[i].nEi; } } return nRet; } void vOut(intnM) { printf("%d ",nM); } intnFind(intnP,intnM) { int i; for(i=1;i<=nM;i++) { if(stuPart[nP].nSi>=stuMachine[i].nEi) { return i; } } return i; }
注意此模型与前边的联系与区别，总结一般的规律，应用到实际的算法中。