❶ 贪心算法总结
做了这10道题，其实发现贪心算法没有什么规律，要说有什么共同特点就是都是由局部最优从而推出全局最优，每个题基本上都要考虑其局部最优是什么，其全局最优是什么，所以虽然都用到了贪心算法的思想，但是题与题之间又没有什么规律可言。
现在把这10道题的思路总结一下（总结主要以我的主观看法在写，可能别人看会不知道我在说什么）
1.分发饼干：
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
思路：想要完成最多的小孩满足，那么就得最小的饼干给胃口最小的小孩
这里的贪心思想，
局部最优就是尽可能让一个饼干喂饱一个
全局最优就是最多的小孩满足
2.摆动序列：
https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
思路：这里要找到最长的摆动序列，那么其实就是找那些波峰波谷，如图所示
可以看出来，在到达波峰波谷的路上有几个数字不会影响什么，可以直接去掉。
那么这里的局部最优就是把单调坡上的点删掉，保留最多的波峰波谷
全局最优就是得到对多的波峰波谷，即最长的摆动序列
3.最大子序和
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
这道题显然可以暴力解出来，即列出所有子序和，找出最大的，不过计算量会比贪心大很多。
这里主要介绍贪心解的思想：
想要得到最大子序和，就得保证每次相加时，相加后不能为负数，因为负数继续往下加一定是拉低总和的，那么我们当加成到负数时就重新从下个数开始加，并实时记录最大的子序和，这样一遍循环就能得出最大子序和。
局部最优：加成负数就立刻停止，并从下个元素重新开始
全局最优：得到最大子序和
4.买卖股票的最佳时机II
https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
思路：想要得到最大利润，那就要低价买入高价卖出，那么怎样的买卖才能得到最大利润呢。
这里就体现出贪心算法的“贪”字（我猜的），这道题贪在哪呢，贪在只要有利可图就去做，即只要今天买入的价钱比明天卖出的价钱底，即有利可图，那么我就去做，做就是在今天买入，在明天卖出。
局部最优：得到每天的最大正利润
全局最优：得到最大利润
5.跳跃游戏
https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
思路：每个数组的元素代表的是可以跳的最远下标，那么我们只要使那个最远下标包含最后一个下标就是可以跳到，那么我们每跳到一个位置就要更新那个可以跳的范围，即可以跳到的最远下标。
局部最优：每次跳跃都得出最远的跳跃范围
全局最优：最后能跳到的最大范围
6.跳跃游戏II
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
思路：这道题要得到最小的跳跃数，其实只要保证跳的是位置是可以跳范围内更新最远范围的位置就可以了。
为什么这么说呢？以题例来说：
我们刚开始在‘0’的位置，我们能跳到‘1’和‘2’的位置，那么我们怎么跳呢？可以看到跳到‘1’之后更新的最大范围是‘4’，跳到‘2’之后更新的最大范围是‘3’，所以我们就跳‘2’了，因为跳‘1’之后更新的最大可跳范围更大包含了跳‘2’的最大可跳范围，那么肯定是跳‘3’最优呀，这里就体现了局部最优的思想。
局部最优：每次跳后，更新的最大可调范围最大
全局最优：跳跃次数最少
7.K次取反后最大化的数组和
https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
思路：想要得到最大数组和，我们就可以想到怎样做呢？
一，尽可能保证负数最少
二，负数绝对值大的优先变正
三，正数绝对值小的优先变负，有零变零
本着这三条原则做，就能做出来。
那么这道题体现了什么贪心思想呢？
我感觉，前面那三条都是贪心中‘贪’的体现
在负数中，局部最优就是：绝对值大的负数优先变正
在正数中，局部最优就是：绝对值小的正数变负，有零变零
得到的全局最优：数组和最大
8.加油站
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
思路：首先可以想到这道题是可以暴力解出来了，即分别以每个加油站为起点，得出可以跑一圈的加油站
那么贪心思想做，该怎么做呢，首先可以想到，如果以一个1点为起点当跑着跑着跑到3，油变为负数时，那么说明以这个起点是不行的，但是以2或3为起点行不行呢？答案肯定是不行的，因为1跑到3，油变为负，说明1~3的gas=0的，所以可以得出，如果1~3油数变为负数，那么由2~3油数肯定也为负数。
所以这里就可以得出，如果经过几个加油站油数变为负了，那么起点就更新为这一段路的下个加油站跑
局部最优：油量一旦为负，就从下个加油站重新跑
全局最优：得出可以跑一圈的加油站起点
9.分发糖果
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
思路：每个孩子至少一个，如果一个孩子比他旁边的孩子优秀，就要比他旁边的糖果多，这道题一旦两边都考虑很容易顾此失彼，所以我们就定义两个循环，分别从左到右，从右到左去考虑，只要更优秀则比他旁边的多1，如果已经多了就不用变了。
局部最优：保证优秀的孩子比他旁边的孩子糖果多
全局最优：满足题中条件，至少要发的糖果
10.柠檬水找零
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
思路：我们在找零时要遵守的规则一定是：
5 得5
10 得10减5
15 得15，优先减一个10减一个5 如果10块没有则减三个5
局部最优：以最少用的5块的方式找零
全局最优：得到找零能否进行下去
❷ 贪心算法总结 Greedy Algorithms
反证法：乱正
假设贪心不是最优解：
先考虑如何排序
Exchange argument:通过交换元素将最优解转换为贪心解，但还保持最优性
当cache中不存在所需元素时，需要访问cache交换元素。
目标：cache misses的次数最少
最优算法：cache miss时替换当前future queries中最远访问的元素。
e.g. future queries中第一个元素g出现cache miss, 需要exchange，判断current cache中需要替换哪个元素。
在future queries中
思路：构造最优规划 ，它有最小的cache misses次数；Farthest-In-Future规划 ,两者在前 个请求的序列是相同的，如果能证明在第 步时， 可以转化为 并且没有增加cache misses的次数，则可以说明 是最优解。
最开始，假设 和 中元素如下：
Case 1: 元素已经在Cache中
假设下一个请求的元素是d显然两者都不会发生cache miss，故两者总的cache misses次数还是相同；
Case 2: 元素不在Cache中， 和 与外界哗李悔交换相同的元素
假设下一个请求的元素是e,两者都用a与其交换，有
和 都增加了一次扰扒cache misses，故总cache misses次数还是相同；
Case 3: 元素不在Cache中， 和 与外界交换不同的元素
假设下一个请求的元素是e, 交换a, 交换b,有
之后，下一个请求的元素有四种情况：
Case 3a: 元素在 中, 不在 中; S交换a
也就是请求b,这时S用a交换b,有
有两次cache misses，而 只有一次，之后 和 序列又保持一致；
Case 3b: 元素在 中, 不在 中; S不交换a
也就是请求b，S用c交换b，有
用a交换c，有
两者cache misses次数相同，之后 和 序列又保持一致
Case 3c: 元素在 中, 不在 中
即请求a，这种情况不可能发生，因为S_{FF}移出的是最远需要的元素，即request中a会排在b之后；
Case 3d: 元素不在 和 中
假设请求f, 用a交换f, 用b交换f,有
两者cache misses次数相同，之后 和 序列又保持一致
的cache misses次数不会多于最优解 , 即 是最优解。
Single-link k-clustering 算法：
❸ 贪心算法及其应用
求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。
比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装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]，期望值就是尽可能多的区间。
我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。
贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。
❹ (三) 贪心算法
贪心算法的思想非常简单且算法效率很高，在一些问题的解决上有着明显的优势。
假设有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就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。
❺ 5. 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1<=i<=n。应如何安排n个顾客的服务次序才能
上面的 思路不错
最优服务次序问题
一、问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1≦i ≦n 。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。
二、贪心选择策略
假设原问题为T，而我们已经知道了某个最优服务系列，即最优解为A={t(1)，t(2)，…．t(n)}(其中t(i)为第i个用户需要的服务时间)，则每个用户等待时间为：
T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；
那么总等待时问，即最优值为：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)；
由于平均等待时间是n个顾客等待时间的总和除以n，故本题实际上就是求使顾客等待时间的总和最小的服务次序。
本问题采用贪心算法求解，贪心策略如下：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T’。新问题和原问题相同，只是问题规模由n减小为n-1。基于此种选择策略，对新问题T’，选择n-1顾客中选择服务时间最短的先进行服务，如此进行下去，直至所有服务都完成为止 。
三、问题的贪心选择性质
先来证明该问题具有贪心选择性质，即最优服务A中t(1)满足条件：t(1)<=t(i)(2<i<n)。
用反证法来证明：假设t(1)不是最小的，不妨设t(1)>t(i)(i>1)。
设另一服务序列B=（t(i)，t(2)，…，t(1)…，t(n)）
那么TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0
即TA>TB，这与A是最优服务相矛盾。
故最优服务次序问题满足贪心选择性质。
四、问题的最优子结构性质
在进行了贪心选择后，原问题T就变成了如何安排剩余的n-1个顾客的服务次序的问题T’，是原问题的子问题。
若A是原问题T的最优解，则A’={t(2)，…t(i)…t(n))是服务次序问题子问题T’的最优解。
证明：假设A’不是子问题T’的最优解，其子问题的最优解为B’，则有TB’<TA’，而根据TA的定义知，TA’十t(1)=TA。因此TB’+t(1)<TA’+t(1)=TA，即存在一个比最优值TA更短的总等待时间，而这与TA为问题T的最优值相矛盾。因此，A’是子问题T’的最优值。
从以上贪心选择及最优子结构性质的证明，可知对最优服务次序问题用贪心算法可求得最优解。
根据以上证明，最优服务次序问题可以用最短服务时间优先的贪心选择可以达到最优解。故只需对所有服务先按服务时间从小到大进行排序，然后按照排序结果依次进行服务即可。平均等待时间即为TA/n。
五、算法实现
由多处最优服务次序问题具有贪心选择性质和最优子结构性质，容易证明算法greedy的正确性。本算法采用最短服务时间优先的贪心策略。首先将每个顾客所需要的服务时间从小到大排序。然后申请2个数组：st[]是服务数组，st[j]为第j个队列上的某一个顾客的等待时间；su[]是求和数组，su[j]的值为第j个队列上所有顾客的等待时间；
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;//循环分配顾客到每一个服务点上
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
六、算法测试结果
七、算法复杂性分析
程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其中，贪心算法部分只有一重循环影响时间复杂度，其时间复杂度为O(n)：而排序算法的时间复杂度为O(nlogn)。因此，综合来看算法的时间复杂度为O(nlogn)。
八、参考文献
[1] 王晓东.计算机算法设计与分析(第3版)[M]．北京：电子工业出版社,2007．
[2] 陈媛.《算法与数据结构》[M],清华大学出版社, 第1版,2005.4.
[3] 王晓东.算法设计与实验题解 [M]．北京：电子工业出版社,2008．
附录（程序代码）
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
void main()
{int n;//等待服务的顾客人数
int s;//服务点的个数
int i;
int a;
int t;//平均服务时间
vector<int>x;
cout<<"please input the num of the customer:"<<endl;
cin>>n;
cout<<"please input the num of the server:"<<endl;
cin>>s;
cout<<"please input the need service time of each customer:"<<endl;
for(i=1;i<=n;i++){
cout<<"No."<<i<<endl;
cin>>a;
x.push_back(a);
}
t=greedy(x, s);
cout<<"the least average waiting time is:"<<t<<endl;
}