❶ C语言程序问题——活动安排问题
题目出得不严密，题目要求是“计算安排的活动最多时会场使用时间”，但当“安排的活动最多”有多种安排方式，题目中却没说输出这多种方式中的哪一种的会场使用时间。例如 ：当有3项活动要安排，开始时间和结束时间分别是1 2、3 5、4 5，这时可以安排第一项和第二项活动，也可以安排第一项和第三项活动，前者的会场使用时间是5，后者是4，这时是输出4还是5，题目中没用指出。先假设测试数据不会出现上述情况，则利用贪心算法求解活动安排问题是一种最常用的方法：#include<stdio.h>
#include<stdlib.h>
struct activity
{
int start;
int end;
}act[8501];
int comp(const void *p, const void *q)
{
struct activity *a=(struct activity *)p;
struct activity *b=(struct activity *)q;
return a->end-b->end;
}
int main()
{
int i,k,res,e;
while(scanf("%d",&k)!=EOF)
{
for(i=0;i<k;i++) scanf("%d%d",&act[i].start,&act[i].end);
qsort(act,k,sizeof(act[0]),comp);
res=act[0].end-act[0].start+1;
e=act[0].end;
for(i=1;i<k;i++)
{
if(act[i].start>e)
{
res+=act[i].end-act[i].start+1;
e=act[i].end;
}
}
printf("%d\n",res);
}
return 0;
}
❷ 哈夫曼编码（贪心算法）
参考： 哈夫曼编码
哈夫曼编码是一种十分有效的编码方法，广泛应用于 数据压缩 中
通过采用 不等长 的编码方式，根据 字符频率的不同 ，选择 不同长度的编码 ，对频率 越高 的字符采用 越短 的编码实现数据的高度压缩。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。
下面看一个例子：
假如我们有一个包含1000个字符的文件，每个字符占1个byte(1byte=8bits)，则存储这100个字符一共需要8000bits。这还是有一些大的
那我们统计一下这1000个字符中总共有多少种字符，原来需要8bit来表示一个字符，如果使用更少的位数来表示这些字符，则可以减少存储空间。
假设这1000个字符中总共有a、b、c、d、e、f共6种字符，使用使用3个二进制位来表示的话，存储这1000个字符就只需要3000bits，比原来更节省存储空间。
或许还可以再压缩一下：
根据字符出现的 频率 给与字符 不等长 的编码，频率越高的字符编码越短，频率越低的字符编码越长。
它不能像等长编码一样直接按固定长度去读取二进制位，翻译成字符，为了能够准确读取翻译字符，它要求一个字符的编码不能是另外一个字符的前缀。
假设a、b、c、d、e、f这6个字符出现的频率依次降低，则我们可以给与他们这样的编码
假如字符的出现频率如图所示，按照这样的编码表示的话，总位数如图，一共2100bits，更加节省空间了
贪心策略：频率小的字符，优先入队。
步骤：
1.将每一个字符作为节点，以出现频率大小作为权重，将其都放入 优先队列 中（一个最小堆）；
2.每次出队两个节点并创建一个父节点，使其权值为刚刚出队的节点的权值和，并且为两个节点的父节点（合并）。然后将这个树入队。
3.重复操作2，直到队列中只有一个元素（此时这个元素表示形式应该为一个树）时，完成创建。
创建好了树，该怎么编码呢？
我们对一个哈夫曼树，从父节点开始的所有节点，往左边标0，右边标1。那么到达叶子节点的顺次编码就可以找到了。
C：字符集合
Q：优先队列
EXTRACT-MIN：传入一个队列，出队最小的元素
INSERT：将z插入到Q中
当for循环结束之后，此时队列中只有一个元素，就是我们需要的哈夫曼树，最后返回此树即可。
假设T树已经是一个最优的树，假设x、y的频率小于等于最低处的a、b，然后交换x、a，y、b。
计算代价是否发生变化。
比如这里比较 T 变成 T ’ 后代价是否变化，发现代价变小或不变。
同理T’到T’’，又因为T本来假设就是最优的，所以只能相等
所以T’’也应该符合条件，即贪婪算法，每次取最小的两个节点出来这种做法是正确的
❸ 5.贪心算法的核心思想。6.什么是递归什么是迭代两者的区别，举例说明。7.回溯的含义是什么举例
1、贪心算法主要是把问题分成很多局部问题，用局部最优解合成整体最优解。因此使用这种算法需要此问题满足两个条件，一个是能够分成多个能够求解的局部问题，第二个就是局部问题的解能够合成最优解。和动态规划、回溯等相比差别就是再不回溯的前提下找出整体最优解或者接近最优解，速度快但应用有比较大的限制。
2、迭代也叫递推，通过重复执行某一步骤或者函数来求得计算结果
递归是指函数中直接或者间接调用自身
举例：
求a乘以2的10次方等于几
迭代：
for (i=0;i<10;i++)
a *= 2;
递归：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}
db(a,0);
3、回溯的含义就是在搜索问题的状态过程中，如果不能继续前进，再向后回到岔口，换一条路继续搜索，直到搜索完所有状态或者查找到需要的状态。
举例：（最典型的就是树的深度搜索，下面举一个简单的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//从3开始查找1
int read[10]=(0);//是否查找过
int readNum = 0;//查找过的个数
int forward = 1;//1为左，2为右
int tmp = 0,index = 5;
tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}
if (index <=0 || index>=9)
forward = 3 - forward;
}
❹ 贪心思想
在学习数据结构的时候，我们已经见过了贪心思想在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的情况下，让总价值尽可能的高。每个物体都可以只取一部分。
我们可以考虑重量和价值的比值作为单价。
❺ 一道数学建模题
我有一个贪心算法，就是说由于不论加班与否都是P1产品的利润高，因此为了满足利润应该尽量在非加班时间生产P1产品，如此一来，P2产品的利润应该是>=7*75=525，剩下的利润还有3500-525=2975
如果A,B组都在非加班时间生产A产品，则可生产10*8+8*8=144kg，利润为144*20=2880，还差95的利润，即95/15=6或7kg，由于B的生产能力是8kg/h，所以7/8>7/10，所以由B生产8千克，此时P1的生产任务完成
再看P2，有75千克的生产任务，此时A组剩下4小时，B组3小时，折合一共生产47kg，不达生产要求
此算法应该是考虑到利润最大化，而又尽量满足生产任务的，因此应该没有无法分配满足题目要求的工作计划
仅供参考
❻ (三) 贪心算法
贪心算法的思想非常简单且算法效率很高，在一些问题的解决上有着明显的优势。
假设有3种硬币，面值分别为1元、5角、1角。这3种硬币各自的数量不限，现在要找给顾客3元6角钱，请问怎样找才能使得找给顾客的硬币数量最少呢？
你也许会不假思索的说出答案：找给顾客3枚1元硬币，1枚5角硬币，1枚1角硬币。其实也可以找给顾客7枚5角硬币，1枚1角硬币。可是在这里不符合题意。在这里，我们下意识地应用了所谓贪心算法解决这个问题。
所谓贪心算法，就是 总是做出在当前看来是最好的选择(未从整体考虑) 的一种方法。以上述的题目为例，为了找给顾客的硬币数量最少，在选择硬币的面值时，当然是尽可能地选择面值大的硬币。因此，下意识地遵循了以下方案：
（1）首先找出一个面值不超过3元6角的最大硬币，即1元硬币。
（2）然后从3元6角中减去1元，得到2元6角，再找出一个面值不超过2元6角的最大硬币，即1元硬币。
（3）然后从2元6角中减去1元，得到1元6角，再找出一个面值不超过1元6角的最大硬币，即1元硬币。
（4）然后从1元6角中减去1元，得到6角，再找出一个面值不超过6角的最大硬币，即5角硬币。
（5）然后从6角中减去5角，得到1角，再找出一个面值不超过1角的最大硬币，即1角硬币。
（6）找零钱的过程结束。
这个过程就是一个典型的贪心算法思想。
贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的 局部最优解 ，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。）
贪心算法没有固定的算法框架，算法设计的关键是 贪心策略的选择 。选择的贪心策略必须具备无后效性。
贪心策略 适用的前提 是：
严格意义上讲，要使用贪心算法求解问题，该问题应当具备以下性质：
注意 ：对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。
因此， 选择能产生问题最优解的最优量度标准是使用贪婪算法的核心 。
实际上，贪心算法 适用的情况很少 。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
最优解问题大部分都可以拆分成一个个的子问题(多阶段决策问题)，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。
贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。
动态规划方法代表了这一类问题的一般解法， 自底向上 构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。
而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始( 自顶向下 )，选择最优的路，一直走到底就可以了。
一个问题分为多个阶段，每个阶段可以有n种决策，各个阶段的决策构成一个决策序列，称为一个策略。
这两种算法都是选择性算法，在进行决策的选择时：
前提是这个问题得具有贪心选择性质，需要证明(数学归纳法(第一、第二))，如果不满足那就只能使用动态规划解决。(一旦证明贪心选择性质，用贪心算法解决问题比动态规划具有更低的时间复杂度和空间复杂度。)
从范畴上来看：
Greedy ⊂ DP ⊂ Searching （贪心是动规的特例）
即所有的贪心算法问题都能用DP求解，更可以归结为一个搜索问题，反之不成立。
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解，与回溯法等比较，它的适用区域相对狭窄许多，因此正确地判断它的应用时机十分重要。
一步一步地进行，常 以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况 ，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
它采用 自顶向下 ，以 迭代 的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以 贪心法不需要回溯 。
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。
❼ 贪心算法及其应用
求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。
比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装100KG重量的袋子，怎么装才能使得袋子中的豆子价值最大？
我们首先看看这个问题是否符合贪心算法的使用场景？限制值是袋子100KG，期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法，每一个步骤都寻找当下的最优解，怎么做呢？
把仓库里面的每种豆子价值除以重量，得出每种豆子的单价，那么当下的最优解，肯定是尽可能最多地装单价最贵的，也就是先把20KG的黄豆都装上，然后再把30KG的绿豆都装上，再装50KG的红豆，那么此时正好装满袋子，总价值将是270元，这就是通过贪心算法求解的答案。
贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证，我们不用那样，只要心里举几个例子，验证下是否比它更好即可，如果举不出例子，那么就可以认为这就是最优解了。
虽然贪心算法虽然在大部分实践场景中都能得到最优解，但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径，那么答案肯定就是S->A->E->T，总代价为1+4+4=9；
然而，实际上的最短路径是S->B->D->T，总代价为6。
所以，不能所有这类问题都迷信贪心算法的求解，但其作为一种算法指导思想，还是很值得学习的。
除了以上袋子装豆子的问题之外，还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题，即找到问题的限制值和期望值。
我们有m个糖果要分给n个孩子，n大于m，注定有的孩子不能分到糖果。其中，每个糖果的大小都不同，分别为S1,S2,S3...,Sm，每个孩子对糖果的需求也是不同的，为N1,N2,N3...,Nn，那么我们如何分糖果，才能尽可能满足最多数量孩子的需求？
这个问题中，限制值是糖果的数量m，期望值满足最多的孩子需求。对于每个孩子，能用小的糖果满足其需求，就不要用大的，避免浪费。所以我们可以给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。
我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张，现在要购买一个价值K元的东西，请问怎么才能适用最少的纸币？
这个问题应该不难，限制值是各个纸币的张数，期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱，当再加一张100元就超过K时，就更换小面额的，直至正好为K元。
对于n个区间[L1,R1],[L2,R2]...[Ln,Rn]，我们怎么从中选出尽可能多的区间，使它们不相交？
我们需要把这个问题转换为符合贪心算法特点的问题，假设这么多区间的最左端点是Lmin，最右端点是Rmax，那么问题就是在[Lmin,Rmax]中，选择尽可能多的区间往里面塞，并且保证它们不相交。这里，限制值就是区间[Lmin,Rmax]，期望值就是尽可能多的区间。
我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。
贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。
❽ 高分悬赏贪心算法的作业
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。 ?
2、[单源最短路径]一个有向图G，它的每条边都有一个非负的权值c[i,j]，“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。
E.Dijkstra发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S中只含源。
设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。
每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解 。
stra.pas
3、[机器调度]现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表：
任务 a b c d e f g
开始(si) 0 3 4 9 7 1 6
完成(fi) 2 7 7 11 10 5 8
在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件，求出最优分配。
?三、练习题：
已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城市的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿该航线已行的耗油量，并假定从城市i到j和城市j到i之间的耗油量是相同的。
分析：
1. 运用贪心思想：
在每一步前进的选择上，选取相对当前城市耗油量最小的航线；
2. 图解：若从1出发，有图：
总耗油量=14 1-2-5-3-4-1
但若路线改为：1-5-3-4-2-1，则总耗油量=13
所以，这样的贪心法并不能得出最佳解。
3. 改善方案：
从所有城市出发的信心过程，求最优的。
编程：
1. 数据结构：
城市联系网络图的描述(图的邻接矩阵的描述)：
const
c=array[1..5,1..5] of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 贪心过程：
begin
初始化所有城市的算途径标志；
设置出发城市V；
for i:=1 to n-1 do {n-1个城市}
begin
s:=从V至所有未曾到过的城市的边集中耗油量最少的那个城市；
累加耗油量；
V:=s；
设V城市的访问标志；
end;
最后一个城市返回第一个城市，累加耗油量；
end;
3. 主过程：实现改善方案
begin
for i:=1 to n do
begin
cost1:=maxint; {初始化}
调用贪心过程，返回本次搜索耗油量cost；
if cost<cost1 then 替换；
end;
输出；
end
❾ 最佳调度问题（c/c++）
如果各机器运行速度相等，换句话就是任务无论在哪台机器上运行完成时间都相等，则问题较简单
1 . 先将任务由大到小排序
2 . 计算n个任务需要的总时间和平均到k个机器上的时间
3 . 将大于平均时间的任务各分配一个机器，找到最大完成时间
4 . 将其他任务顺序安排在一台机器上，如果时间超出最大时间，则把该任务交给下一个机器，下一个任务继续在这台机器上试安排，直到所有任务都不能在小于最大完成时间的情况下安排
5 . 安排下一台机器直道所有任务安排完，
6 . 或有可能安排某(些)任务找不到小于最大完成时间 那么重新扫描各台机器使再加上该任务后时间最小，按此方法安排万所有任物
数据结构采用链表比较合适，
K个机器k个链，n个任务按大小顺序插入一个链表，安排后从任务链表中移动到机器链表中。知道链表为空
❿ 程序员算法基础——贪心算法
贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。
比如一道常见的算法笔试题---- 跳一跳 ：
我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。
本文即是对这种贪心决策的介绍。
狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。 能用贪心解决的问题，也可以用动态规划解决。
而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：
我们发现的题目的核心在于 向右能到达的最远距离 ，我们用maxRight来表示；
此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。
贪心的思考过程类似动态规划，依旧是两步： 大事化小 ， 小事化了 。
大事化小：
一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；
小事化了：
从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的 向右能到达的最远距离 ；
在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。
如果是动态规划：
要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。
似乎有些不对？ 平时我们找零钱有这么复杂吗？
从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。
从日常生活的经验知道，这么做是正确的，但是为什么？
假如我们把题目变成这样，原来的策略还能生效吗？
接下来我们来分析这种策略：
已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；
假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（z<c），且纸币张数更少（x+y+z<a+b+c），即是用更少5元纸币得到最优解。
我们令k=5*(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币；（因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张）
容易知道，减少(c-z)张5元纸币，需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。
由此我们知道不可能存在使用更少5元纸币的更优解。
所以优先使用大额纸币是一种正确的贪心选择。
对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4；（1+1+1+7）
但如果只使用5元纸币，则张数是2；（5+5）
在这种情况下，优先使用大额纸币是不正确的贪心选择。（但用动态规划仍能得到最优解）
如果是动态规划：
前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。
我们用 dp[i]表示前i秒能完成的任务数 ；
在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：
1、不执行这个任务，那么dp[i]没有变化；
2、执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如说对于任务j如果是第5秒开始第10秒结束，如果i>=10，那么有 dp[i]=max(dp[i], dp[5] + 1)； （相当于把第5秒到第i秒的时间分配给任务j）
再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情？我换一种描述方式：
我们自然而然会想到一个策略： 先把结束时间早的兼职给做了！
为什么？
因为先做完这个结束时间早的，能留出更多的时间做其他兼职。
我们天生具备了这种优化决策的能力。
这是一道 LeetCode题目 。
这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。
因为（前i个人的最少糖果数）这种状态表示会收到第i+1个人的影响，如果a[i]>a[i+1]，那么第i个人应该比第i+1个人多。
即是 这种状态表示不具备无后效性。
如果是我们分配糖果，我们应该怎么分配？
答案是： 从分数最低的开始。
按照分数排序，从最低开始分，每次判断是否比左右的分数高。
假设每个人分c[i]个糖果，那么对于第i个人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高）
但是，这样解决的时间复杂度为 O(NLogN) ，主要瓶颈是在排序。
如果提交，会得到 Time Limit Exceeded 的提示。
我们需要对贪心的策略进行优化：
我们把左右两种情况分开看。
如果只考虑比左边的人分数高时，容易得到策略：
从左到右遍历，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。
再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：
如果a[i]>a[i+1], 则有c[i]=c[i+1]+1；否则c[i]不变；
这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是 O(N) 。
题目给出关键信息：1、两个人过河，耗时为较长的时间；
还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去；
要保证总时间尽可能小，这里有两个关键原则： 应该使得两个人时间差尽可能小（减少浪费），同时船回去的时间也尽可能小（减少等待）。
先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配？
答案： 每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。
再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时A<B<C。
那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）
如果有A/B/C/D四个人，且耗时A<B<C<D，这时有两种方案：
1、最快的来回送人方式，A+B去；A回；A+C去，A回；A+D去； 总耗时是B+C+D+2A （减少等待原则）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；总耗时是 3B+D+A （减少浪费原则）
对比方案1、2的选择，我们发现差别仅在A+C和2B；
为何方案1、2差别里没有D？
因为D最终一定要过河，且耗时一定为D。
如果有A/B/C/D/E 5个人，且耗时A<B<C<D<E，这时如何抉择？
仍是从最慢的E看。（参考我们无限多船的情况）
方案1，减少等待；先送E过去，然后接着考虑四个人的情况；
方案2，减少浪费；先送E/D过去，然后接着考虑A/B/C三个人的情况；（4人的时候的方案2）
到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。
根据5个人的情况，我们可以推出状态转移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);
由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。
贪心的学习过程，就是对自己的思考进行优化。
是把握已有信息，进行最优化决策。
这里还有一些收集的 贪心练习题 ，可以实践练习。
这里 还有在线分享，欢迎报名。