⑴ 贪心算法 活动安排问题
这道题的贪心算法比较容易理解，我就不多说明了，只是提到一下算法思路1、建立数学模型描述问题。我在这里将时间理解成一条直线，上面有若干个点，可能是某些活动的起始时间点，或终止时间点。在具体一下，如果编程来实现的话，将时间抽象成链表数组，数组下标代表其实时间，该下标对应的链表代表在这个时间起始的活动都有哪些，具体参照程序注释。2、问题分解。为了安排更多的活动，那么每次选取占用时间最少的活动就好。那么从一开始就选取结束时间最早的，然后寻找在这个时间点上起始的活动，以此类推就可以找出贪心解。程序代码：#include<stdio.h>
struct inode //自定义的结构体
{
int end; //表示结束时间
inode *next; //指向下一个节点的指针
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num负责计数，i控制循环，a，b输入时候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //输入并建立数据结构
{
if(a==0&&b==0) break;
pt=new inode; //创建新的节点，然后将该节点插入相应的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //进行贪心算法，i表示当前时间
{
if(start[i].next==NULL)
{
i++; //该时间无活动开始
}
else
{
int temp=10001; //临时变量，存储该链表中最早的终止时间
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //将当前时间设置成前一子问题的终止时间
num++;
}
}
printf("%d\n",num); //打印结果
return 0;
}代码并不一定是最快速的，但是可以求出贪心解，如果你做的是ACM编程题目，不保证能AC注释我尽力写了，希望对你有帮助。
⑵ 数据结构之贪心算法
贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
贪婪算法：当下做局部最优判断，不能回退
（能回退的是回溯，最优+回退是动态规划）
由于贪心算法的高效性以及所求得答案比较接近最优结果，贪心算法可以作为辅助算法或解决一些要求
结果不特别精确的问题
注意：当下是最优的，并不一定全局是最优的。举例如下：
有硬币分值为10、9、4若干枚，问如果组成分值18，最少需要多少枚硬币？
采用贪心算法，选择当下硬币分值最大的：10
18-10=8
8/4=2
即：1个10、2个4，共需要3枚硬币
实际上我们知道，选择分值为9的硬币，2枚就够了
18/9=2
如果改成：
背包问题是算法的经典问题，分为部分背包和0-1背包，主要区别如下：
部分背包：某件物品是一堆，可以带走其一部分
0-1背包：对于某件物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况。
部分背包问题可以用贪心算法求解，且能够得到最优解。
假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，可以带走某件物品的一部分，请问：他应该选择哪些物品？
假设背包可容纳50Kg的重量，物品信息如下表：
将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品
按照我们的贪心策略，单位重量的价值排序： 物品A > 物品B > 物品C
因此，我们尽可能地多拿物品A，直到将物品1拿完之后，才去拿物品B，然后是物品C 可以只拿一部分.....
在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)
优点：性能高，能用贪心算法解决的往往是最优解
缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的
针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而全局最优）
大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明
在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解
⑶ 贪心思想
在学习数据结构的时候，我们已经见过了贪心思想在Prim和Kruskal中的完美应用，贪心思想因为其的简洁在算法中经常会被用到，有的时候在生活中，我们也会无意中使用到l贪心算法。比如在去shopping时，经常需要进行找零钱的过程，我们总是不自觉的先把大的找出来。
那么什么是贪心思想？
贪心算法总是作出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
只有在满足最优子结构的情况下贪心算法得到的结果才是最优结果。
比如找钱的问题，我要给你一百，那么我尽可能每一次给你最多的。
或者比如磁盘的最优存储问题，所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
Prim和kruskal算法都是每次选择最小的边纳入生成树。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这也是贪心问题和动态规划问题的主要区别。
在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。
可运用贪心策略，选n次，每一次选相应行中的最大值即可。
但是，在一个n*m的方格阵中，每一格子赋予一个数，规定每次移动时只能向上或向右，现试找出一条路径，使其从左下角至右上角所经过的权值之和最大。
同样考虑贪心策略，从左下角向右上角移动，每次移动选择权值较大的一个方向。
以2*3矩阵为例，采用贪心的策略得到的是1,3,4,6和为14但是实际的最优结果为1,2,100,6和为109.
所以说贪心算法并不是总是可行，证明当前问题存在贪心选择性质（全局最优解可以通过局部最优贪心选择达到）和最优子结构性质（问题的最优解包含了其子问题的最优解）。所以贪心问题如果当前的选择不会干扰之后的选择，则不会出现问题。
其他的情况就需要进行证明，证明的最好办法就是将最小子问题进行一步步的合并，直到最后还原为最后的原问题，若所得到的解是总体最优的则可以使用贪心思想，否则不可以。
比如上面的问题，我们的走一步的最优解为1，3，然后我们判断一次走两步的最优解是否任然为1,3这个路径，答案显然不是，变为 1,2,100这个路径，所以显然不能使用贪心思想。
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。
有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。
部分背包问题， 有n个物体，第i个物体重量为wi,价值为vi,在总重量不超过C的情况下，让总价值尽可能的高。每个物体都可以只取一部分。
我们可以考虑重量和价值的比值作为单价。