贪心算法） 一、基本概念： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是
贪心算法）
一、基本概念：
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步） { 利用可行的决策，求出可行解的一个解元素； } 由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
例题：
问题一、活动安排问题
问题表述：
设有n个活动的集合e = {1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。输入每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且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的规模最大。这个结论可以用数学归纳法证明。
实现代码（我还看不懂啊~~~~~~）： 代码/* 主题：活动安排问题* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：c++* 开发环境：vicrosoft visual studio* 时间: 2010.11.21*/#include #include #include using namespace std ;struct activitytime{public: activitytime (int nstart, int nend) : m_nstart (nstart), m_nend (nend) { } activitytime () : m_nstart (0), m_nend (0) { } friend bool operator const activitytime& lth, const activitytime& rth) { return lth.m_nend public: int m_nstart ; int m_nend ;} ;class activityarrange {public: activityarrange (const vector& vtimelist) { m_vtimelist = vtimelist ; m_ncount = vtimelist.size () ; m_bvselectflag.resize (m_ncount, false) ; } // 活动安排 void greedyselector () { __sorttime () ; // 第一个活动一定入内 m_bvselectflag[0] = true ; int j = 0 ; for (int i = 1; i if (m_vtimelist[i].m_nstart > m_vtimelist[j].m_nend) { m_bvselectflag[i] = true ; j = i ; } } copy (m_bvselectflag.begin(), m_bvselectflag.end() ,ostream_iteratorbool> (cout, )); cout private: // 按照活动结束时间非递减排序 void __sorttime () { sort (m_vtimelist.begin(), m_vtimelist.end()) ; for (vector::iterator ite = m_vtimelist.begin() ; ite != m_vtimelist.end() ; ++ ite) { cout m_nstart , m_nend private: vector m_vtimelist ; // 活动时间安排列表 vectorbool> m_bvselectflag ;// 是否安排活动标志 int m_ncount ; // 总活动个数} ;int main(){ vector vactitimelist ; vactitimelist.push_back (activitytime(1, 4)) ; vactitimelist.push_back (activitytime(3, 5)) ; vactitimelist.push_back (activitytime(0, 6)) ; vactitimelist.push_back (activitytime(5, 7)) ; vactitimelist.push_back (activitytime(3, 8)) ; vactitimelist.push_back (activitytime(5, 9)) ; vactitimelist.push_back (activitytime(6, 10)) ; vactitimelist.push_back (activitytime(8, 11)) ; vactitimelist.push_back (activitytime(8, 12)) ; vactitimelist.push_back (activitytime(2, 13)) ; vactitimelist.push_back (activitytime(12, 14)) ; activityarrange aa (vactitimelist) ; aa.greedyselector () ; return 0 ;}
2.快速幂算法
matrix qmpow(matrix &a, int n){ matrix rslt(a.n); rslt.unit(); if(n == 0) return rslt; while(n) { if(n & 1) // 若幂为奇数 { rslt = rslt * a; } a = a * a; n >>= 1; // 右位移等价于除以2 } return rslt;}