贪心算法概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。基本概念
一、基本思路1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。二、适用问题贪心策略适用的前提是：局部最优策略能导致产生全局最优解。三、实现框架从问题的某一初始解出发；while（能朝给定总目标前进一步）{利用可行的决策，求出可行解的一个解元素；}由所有解元素组合成问题的一个可行解；简要介绍
四、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
最优装载问题#includeiostream
#includealgorithm
usingnamespacestd;
intw[1001],c,n;
intmain(){
cincn;
for(inti=1;i=n;i++)
cinw[i];
sort(w+1,w+1+n);
inttemp=0,ans=0;
for(inti=1;i=n;i++){
temp+=w[i];
if(temp=c)
ans++;
else
break;
}
coutans;
return0;
}
最优装载问题2
假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。你没法让这些课都在这间教室上，因为有些课的上课时间有冲突。教室调度问题
你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？这个问题好像很难，不是吗？实际上，算法可能简单得让你大吃一惊。具体做法如下。(1)选出结束最早的课，它就是要在这间教室上的第一堂课。(2)接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。重复这样做就能找出答案！下面来试一试。美术课的结束时间最早，为10:00a.m.，因此它就是第一堂课。
接下来的课必须在10:00a.m.后开始，且结束得最早。英语课不行，因为它的时间与美术课冲突，但数学课满足条件。最后，计算机课与数学课的时间是冲突的，但音乐课可以。
因此将在这间教室上如下三堂课。同学们可能会说，这个算法太容易、太显而易见，肯定不对。但这正是贪婪算法的优点简单易行！贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。对于这个调度问题，上述简单算法找到的就是最优解！显然，贪婪算法并非在任何情况下都行之有效，但它易于实现！
有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少(指每个人的时间之和，包括每个人的等待时间)？【算法分析】由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，就不再赘述），所以这道题可以用贪心法解答，基本步骤：(1)将输入的时间按从小到大排序；(2)将排序后的时间按顺序依次放入每个水龙头的队列中；(3)统计，输出答案。【样例输入】42//4人打水，2个水龙头2645//每个打水时间【样例输出】23//总共花费时间排队打水问题
有N堆纸牌，编号分别为1，2，…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可