贪婪法
）
贪婪法只在很少的情况下得到最优解。但可以作为辅助算法。
贪婪法的设计思想有以下三步：
（1）建立对问题精确描述的数学模型，包括定义最优解的模型；
（2）将问题分解为一系列子问题，同时定义子问题的最优解结构；
（3）应用贪心原则确定每一个子问题的局部最优解，并根据最优解的模型，用子问题的局部最优解堆叠出全局最优解。
0-1背包问题：
有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
首先定义背包问题的数据结构，定义物品的属性：重量和价值。
typedef structtagObject{int weight;int price;int status;//0：未选中；1：已选用；2：已经不可选}OBJECT；
定义背包问题数据结构，属性：可选物品列表，背包总的承重量：
typedef structtagKnapsackProblem{std::vector<OBJECT> objs;int totalC;}KNAPSACK_PROBLEM;
spFun参数是选择策略函数的接口，通过替换这个参数，可以选择不同的策略。
intChoosefunc1(std::vector<OBJECT>& objs, int c) //选择价值优先的方案{int index = -1;//在GreedyAlgo()函数中的while循环的条件判断时，不进入。int mp = 0; //作为price的比较。for(int i = 0;i < static_cast<int>(objs.size()); i++){if((objs[i].status == 0)&& (objs[i].prize > mp)) //状态可选且price比mp大，将mp置为price并将标号赋给index{mp = objs[i].price;index = i;}}return index;}
GreedyAlgo()函数是贪婪算法的主体结构，子问题的分解和选择策略都在这个函数中。可作为这类问题通用解决思路。
void GreedyAlgo(KNAPSACK_PROBLEM*problem,SELECT_POLICY ){int idx;int ntc = 0; //已选物品的重量//spFunc 每次选最符合策略的那个物品，选后再检查while((idx = spFunc(problem->objs,problem->totalC – ntc)) != -1){if((ntc + problem->objs[idx].weight)<= problem->totalC )//若已选的物品重量+正在选的物品重量<=剩余的重量，则把//正在选的物品标记，并将重量加在已选的重量里。{problem->objs[idx].status= 1;ntc+= problem->objs[idx].weight;}else{//不能选这个物品了，做个标记后重新选problem->objs[idx].status= 2}}PrintResult(problem->objs);}
活动安排问题
设有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相容。
由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。
例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
算法greedySelector 的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。活动安排问题实现，各活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非减序排列。如果所给的活动未按此序排列，可以用O(nlogn)的时间重排。：
#include "stdafx.h"#include <iostream> using namespace std; template<class Type>void GreedySelector(int n, Type s[], Type f[], bool A[]);const int N = 11;int main(){//下标从1开始,存储活动开始时间int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};//下标从1开始,存储活动结束时间int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};bool A[N+1];cout<<"各活动的开始时间,结束时间分别为："<<endl;for(int i=1;i<=N;i++){cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;}GreedySelector(N,s,f,A);//得到当前活动是否与上一活动相容的布尔值cout<<"最大相容活动子集为："<<endl;//依次进行判断：如果活动i与已选择的活动相容，则添加i活动for(int i=1;i<=N;i++){if(A[i]){cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;}}return 0;}template<class Type>void GreedySelector(int n, Type s[], Type f[], bool A[]){A[1]=true;int j=1;//记录最近一次加入A中的活动for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容{//如果i的开始时间小于上一活动j的结束时间，则返回ture且j活动被替换为i活动if (s[i]>=f[j]){A[i]=true;j=i;}else{A[i]=false;}}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
像一颗深绿色的宝石镶嵌在云南大地上，
