贪心算法基本思想

① (三) 贪心算法

贪心算法的思想非常简单且算法效率很高，在一些问题的解决上有着明显的优势。

假设有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就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。

② 哈夫曼编码（贪心算法）

参考： 哈夫曼编码

哈夫曼编码是一种十分有效的编码方法，广泛应用于 数据压缩 中
通过采用 不等长 的编码方式，根据 字符频率的不同 ，选择 不差派拿同长度的编码 ，对频率 越高 的字符采用 越短 的编码实现数据的高度压缩。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。

下面看一个例子：
假如我们有虚搭一个包含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’’也应该符合条件，即贪婪算法，每次取最小的两个节点出来这种做法是正确的

③ python里面什么是贪婪

Python里面的贪婪算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，/不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本思路

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本思路

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本思路

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。

④ 贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。

3.2.2.1 贪心算法1

第一步:设置一个记录三角剖分中边的数组T。

第二步:计算点集S中所有点对之间的距离d(p_i，p_j)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d₁，d₂，…，d_n(n-1)/2，相应的线段记为e₁，e₂，…，e_n(n-1)/2，将这些线段存储在数组E中。

第三步:从线段集E中取出长度最短的边e₁存到T中作为三角剖分的第一条边，此时k=1。

第四步:依次从E中取出长度最短的边e_k，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除e_k。这一步运行到S中没有边为止，即至k=n(n-1)/2。

第五步:输出T。

该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n²lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n³)。

3.2.2.2 贪心算法2

第一步:求点集的凸壳，设凸壳顶点为p₁，p₂，…，p_m，凸壳的边为e₁，e₂，…，e_m。并将凸壳顶点按顺序连接成边的e_i加入T(三角剖分的边集合)，并且e_i的权值被赋为1。凸壳内点的集合为S₁={p_m+1，p_m+2，…，p_n}。

第二步:从内部点S₁中任取一点p_i，求与p_i距离最近的点p_j，将线段 存入T。

第三步:求与p_j距离最近的点(除点p_i外)，设为p_k，并将线段 加入T，并将这些边的权值设为1，而w_ij、w_jk和w_ki的值加1，即为2。边的权值为2则表示该边为两个三角形共有。

第五步:对权值为1的边(除e₁，e₂，…，e_m外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1。

第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e₁，e₂，…，e_m外)。

贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求p_k要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)

⑤ 什么是贪心算法

问题一：贪心算法，这个贪心到底是什么意思 贪心指目光短浅，只看到当前这一步的最优决策，而不考虑以后的决策。这样的算法只在特定的问题下是正确的。

问题二：哪些常见算法属于贪婪算法？ 显然KMP和FLOYD算法不是贪心算法，FLOYD算法是使用了类似于动态规划的思想，而KMP算法则是对串的前缀进行去处理得到所有可能出现匹配的位置从而减少不必要的位移。贪心算法可能还有很多，但是一般能用到的可能只有这些。在确定一个问题是否能用贪心来解决的时候应该线能够证明在这里使用贪心算法的正确性（详见算法导论）

问题三：求解一贪心算法问题 最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 问题四：贪心算法的基本思想是什么？ 自己利益最大

问题五：贪心算法是什么？求教学，c语言 jb51/article/71144，里面讲得比较详细

问题六：贪心算法的基本要素是什么，并简单解释其含义 您好，我看到您的问题很久没有人来回答颤运，但是问题过期无人回答会被扣分的并且你的悬赏分也会被没收！销迅所以我给你提几条建议：
一，你可以选择在正确的分类下去提问，这样知道你问题答案的人才会多一些，回答的人也会多些。
二，您可以到与您问题相关专业网站论坛里去看看，那里聚集了许多专业人才，一定可以为你解决问题的。
三，你可以向你的网上好友问友打听，他们会更加真诚热心为你寻找答案的，甚至可以到相关网站直接搜索.
四，网上很多专业论坛以及知识平台，上面也有很多资料，我遇到专业性的问题总是上论坛求解决办法的。
五，将你的问题问的细一些，清楚一些！让人更加容易看懂明白是什么意思!
谢谢采纳我的建议! !

问题七：贪心算法的特性 贪婪算法可解决的问题通常大部分都有如下的特性：⑴随着算法的进行，将积累起其它两个 *** ：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。⑵有一个函数来检查一个候选对象的 *** 是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。⑶还有一个函数检查是否一个候选对象的 *** 是可行的，也即是否可能往该 *** 上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。⑷选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。⑸最后，目标函数给出解的值。⑹为了解决问题，需要寻找一个构成解的候选对象 *** ，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的 *** 为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果 *** 中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到 *** 里。每一次都扩充 *** ，并检查该 *** 是否构成解。如果贪婪算法正确工作，那么找到的第茄斗梁一个解通常是最优的。

⑥ 贪心算法总结

做了这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块的方式找零

全局最优：得到找零能否进行下去

⑦ 程序设计一课中提到的贪婪法基本思想是什么啊

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
贪婪算法的一般方法
1、问题描述
它有n个输入，而它的解就由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。
2、约束条件 那些必须满足的条件称为约束条件。
3、可行解 满足约束条件的子集称为该问题的可行解。
4、目标函数 事先给定的衡量可行解优劣的量度标准，通常以函数的形式给出，称为目标函数。
5、最优解 使目标函数取极值（极大或极小）的可行解，称为最优解。
6、子结构模式 贪心技术中，问题的最优一般是原输入的子集，获取最优子集的贪心方法为子结构模式
7、有序模式 通过计算已有的判定而得出的最优条件，可以为下一步的判定提供依据，这种形式的贪心算法称为有序模式。
8、贪婪算法求解思想（分步处理）
�8�4 根据题意，选取一种量度标准；
�8�4 然后按这种量度标准对这n个输入排序，并按序一次输入一个量。
�8�4 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。
这种能够得到某种意义下的最优解的分级处理方法称为贪心算法。

⑧ 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的情况下，让总价值尽可能的高。每个物体都可以只取一部分。

我们可以考虑重量和价值的比值作为单价。

⑩ 电脑鼠两种算法法则

电脑鼠两种算法法则是贪心算法和动态规划算法，具体如下：
1、贪心算法：贪心算法是一种简单而常用的算法，它的基本思想是在每一步选择中都采取当前状态下最优的选择，以期望最终能够达到全局最优。
2、动态规划算法：动态规划算法是一镇察备种更加复杂和高效的算法，它通过将问题拆分成若干个子没歼问题，并且保御毁存子问题的解，从而避免了重复计算。