下载文档原格式
关于贪⼼算法的研究关于贪⼼算法的研究[摘要] 本⽂对贪⼼算法进⾏较详细的研究。
第⼀部分明确其基本概念，第⼆部分介绍常见的贪⼼模型，第三部分给出常⽤的贪⼼证明⽅式，第四部分介绍贪⼼的经典算法，第五部分与其他算法进⾏⽐较，最后总结贪⼼算法的优劣性、竞赛应⽤及前景。
[关键词] 贪⼼算法、Prim、kruskal、Dijkstra、Huffman、拟阵、证明贪⼼算法是在信息学竞赛中⼀个常⽤的重要算法。
在许多的经典算法中都处处藏着贪⼼的思想。
MST中的Prim和Kruskal都是很优的贪⼼算法。
还有Dijkstra的单源最短路径和数据压缩(Huffman)编码以及Chvatal的贪⼼集合覆盖启发式。
其实很多的智能算法（启发式算法），就是贪⼼算法和随机化算法结合。
这样的算法结果虽然也是局部最优解，但是⽐单纯的贪⼼算法更靠近最优解，例如遗传算法，模拟退⽕算法。
贪⼼算法是与⼈类通常思维⽅式极其相近的算法，所以使⽤贪⼼算法时最⼤的困难通常不是构造贪⼼，⽽是证明贪⼼算法的正确性。
本⽂将对贪⼼算法的模型与包含贪⼼的经典算法进⾏介绍，同时给出贪⼼算法的证明⽅式。
最后总结贪⼼算法的优劣性、竞赛应⽤及前景。
[⽬录]1 贪⼼算法的基本概念 (2)1.1 定义 (2)1.2 基本特性 (2)1.3 基本思路 (2)2 贪⼼模型 (2)2.1 硬币问题 (2)2.2 装载问题 (3)2.3 部分背包问题 (4)2.4 乘船问题 (6)2.5 区间问题 (8)2.6 选点问题 (9)2.7 顺序问题 (11)3 贪⼼证明 (13)3.1 公式法 (13)3.2 交换参数法 (13)3.3 归纳法 (13)3.4 反证法 (13)4 经典贪⼼算法 (13)4.1 Prim (14)4.2 Kruskal (14)4.3 Dijkstra (14)4.4 Huffman (14)5 拟阵 (14)6 贪⼼算法与其他算法的⽐较 (15)6.1 贪⼼与动态规划的⽐较 (15)6.2 基本特性贪⼼与分治的⽐较 (16)7 总结 (16)8 参考⽂献 (16)1 贪⼼算法的基本概念1.1 定义贪⼼算法(Greedy Algorithm)，⼜称贪婪算法，它在对问题求解时，能根据每次所求得的局部最优解，推导出全局最优解或最优⽬标。
《基于贪心算法的动态规划策略》篇一一、引言在计算机科学和优化理论中，动态规划和贪心算法是两种常用的解决优化问题的方法。
动态规划更侧重于通过保存子问题的解来避免重复计算，而贪心算法则倾向于在当前状态下做出最优选择。
本文将探讨如何结合这两种算法的思想，设计一种基于贪心算法的动态规划策略，以解决一些具有挑战性的实际问题。
二、背景及问题阐述在实际生活中，我们常常需要面对一系列具有复杂约束的优化问题。
这些问题通常需要在有限的时间内，通过计算寻找一种最满意的解决方案。
例如，在资源分配、路径规划、网络流等问题中，我们往往需要在满足一定约束条件下，追求某种指标（如成本、时间、效率等）的最优化。
针对这些问题，本文提出了一种基于贪心算法的动态规划策略。
三、贪心算法与动态规划的结合1. 贪心策略贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
它的特点是在每一步选择中都只考虑当前状态，而不从整体最优上加以考虑。
2. 动态规划动态规划是一种通过保存子问题的解来避免重复计算，从而解决最优化问题的方法。
它通常将问题分解为若干个子问题，并保存子问题的解以供后续使用。
结合这两种算法的思想，我们可以设计一种基于贪心策略的动态规划方法。
具体而言，我们可以在动态规划的过程中，利用贪心策略来指导子问题的选择和解决。
这样可以在保证解的质量的同时，提高算法的效率。
四、策略设计及实施1. 问题分解与建模首先，我们需要将问题分解为若干个子问题，并建立相应的数学模型。
这通常涉及到对问题的深入理解和分析，以确定哪些子问题的解对最终结果具有关键影响。
2. 贪心策略的引入在建立数学模型后，我们可以引入贪心策略来指导子问题的选择和解决。
具体而言，我们可以在每一步选择中，根据当前状态和目标函数的特点，选择最有利于达到全局最优的子问题进行处理。
3. 动态规划的实现在引入贪心策略后，我们可以利用动态规划的思想来求解问题。
对k-means聚类算法的改进研究摘要:本文针对k-means算法对初值的依赖性，基于最小生成树原理选取聚类中心进行聚类。
根据寻找最优初值的思想提出了一种改进的k-means算法，将最小生成树的构造算法之一的卡斯克鲁尔（Kruskal Algorithm）算法以及贪心算法(Greedy Algorithm)的思想引入到k-means算法中。
关键字：k-means算法最小生成树贪心策略一、算法的改进思路的形成无论是原始的k-means算法还是加入了聚类准则函数的k-means算法,都有一个共同的特点,即采用两阶段反复循环过程，算法结束的条件是不再有数据元素被重新分配：1)指定聚类，即指定数据x i到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近；2)修改聚类中心。
k-means算法中急需解决的问题主要有三个：(l)在k-means算法中,k是事先给定的，这个k值的选定是很难估计的。
很多时候，我们事先并不知道给定的数据集应分成多少类最合适，这也是k-means 算法的一个不足。
有的算法是通过类的自动合并和分裂，得到较为合理的类型数目k，例如ISODALA算法。
关于k-means算法中聚类数目k值的确定，有些根据方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分墒来验证最佳分类数的正确性。
在文献[26]中，使用了一种结合全协方差矩阵的RPCL算法，并逐步删除那些只包含少量训练数据的类。
而其中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。
它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法，使之远离输入值。
(2)在k-means算法中常采用误差平方和准则函数作为聚类准则函数，考察误差平方和准则函数发现：如果各类之间区别明显且数据分布稠密，则误差平方和准则函数比较有效；但是如果各类的形状和大小差别很大，为使误差平方和的值达到最小,有可能出现将大的聚类分割的现象。
![贪婪算法思想及其应用[5篇模版]](https://img.taocdn.com/s1/m/e84e86f581eb6294dd88d0d233d4b14e85243ed2.png)
贪婪算法思想及其应用[5篇模版]第一篇：贪婪算法思想及其应用贪婪算法思想及其应用摘要：贪婪算法也称作贪心算法，它没有固定的算法框架，算法设计的关键是贪婪策略的选择，并且所选的贪婪策略要具有无后向性。
关键词：贪婪策略，无后向性，最优正文：一．贪婪算法的定义：贪婪算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。
二．贪婪算法思想：贪婪算法采用逐步构造最优解的方法，即在每个阶段，都选择一个看上去最优的策略（在一定的标准下）。
策略一旦选择就不可再更改，贪婪决策的依据称为贪婪准则，也就是从问题的某一个初始解出发并逐步逼近给定的目标，以尽可能快的要求得到更好的解。
而且它在设计时没有固定的框架，关键在于贪婪策略的选择。
但要注意的是选择的贪婪策略要具有无后向性，即某阶段状态一旦确定下来后，不受这个状态以后的决策的影响，也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关。
三．贪婪算法的优缺点：贪婪算法的优点在于在求解问题的每一步它都是选择最优解，这样算法就容易实现也易于理解，同时也提高了效率并节省了时间。
然而贪婪算法的缺点也是不容忽视的，由于它采取逐步获得最优解的方法而不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。
因此贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它都能得出整体最优解或者是整体最优解的近似解。
四.实例参考：下面就列举用贪婪算法成功得出问题最优解的例子：例：一个小孩拿着一美元去商店买糖果，花了33美分，售货员需要找回67美分给小孩，而美分的面值有25,10,5,1这几种。
问题是售货员找个小孩的钱币的个数应是最少的，但同时要满足67美分这个条件。
分析：选择硬币时所采用的贪婪准则如下：每一次都选择面值最大的货币来凑足要找的零钱总数，但前提是不能超出要找的67美分。
解：我们用贪婪算法来处理这个问题，首先我们肯定会选择面值为25的货币，这样的货币我们需要两枚，然后我们依据贪婪准则选择面值为10的货币，这样的货币我们需要一枚，接着继续选择面值为5的货币一枚和面值为1的货币两枚。
贪心算法实验报告心得前言贪心算法是一种常见且重要的算法设计思想，通过每一步都选择当下最优的解决方案，以期望最终得到全局最优解。
在学习与实践贪心算法的过程中，我有了许多心得与体会。
什么是贪心算法？贪心算法是一种求解问题的算法思想，它的特点是每一步都选择当前最优的解决方案，而不考虑该选择对以后步骤的影响。
贪心算法通常适用于可以将问题分解为若干个子问题，并且通过每次选择当前最优解来得到整体最优解的情况。
贪心算法的基本步骤贪心算法的基本步骤可以总结为以下几个方面：1.确定问题的解空间，并找到问题的最优解。
贪心算法通常通过穷举法或者利用问题的特殊性质来确定解空间。
2.制定贪心策略。
贪心算法的核心是确定每一步选择的贪心策略，即选择当前最优解。
3.确定贪心策略的正确性。
贪心算法的一个关键问题是如何证明贪心策略的正确性。
可以通过数学证明、反证法或者举反例等方式来进行证明。
4.实现贪心算法。
将贪心策略转化为实际可执行的算法步骤，编写代码来求解问题。
贪心算法实验结果分析在本次实验中，我使用贪心算法解决了一个经典问题：找零钱问题（Change-Making Problem）。
给定一定面额的硬币和需找的金额，我们的目标是使用最少的硬币来完成找零钱。
贪心算法的思路是每次选择面额最大的硬币进行找零。
实验设计1.实验输入：我设计了多组输入来测试贪心算法的性能。
每组输入包括一个需找的金额和一个硬币集合。
2.实验输出：对于每组输入，贪心算法输出一个最优的硬币找零方案，以及使用的硬币数量。
3.实验评价：我使用了实际需找金额与贪心算法计算得到的找零金额的差值来评估算法的准确性，并统计了算法的时间复杂度。
实验结果从多组实验结果中可以观察到，贪心算法在大部分情况下给出了正确的找零金额，并且算法的时间复杂度较低。
结果分析贪心算法在找零钱问题中的应用是合理的。
每次选择面额最大的硬币进行找零，可以快速接近最优解，并且相对其他算法具有较低的时间复杂度。
《基于贪心算法的动态规划策略》篇一一、引言在计算机科学和优化理论中，动态规划和贪心算法是两种重要的策略。
动态规划通过将问题分解为子问题并存储其解决方案，从而避免了重复计算。
而贪心算法则是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
本文将探讨如何结合这两种策略，特别是在某些复杂问题中，基于贪心算法的动态规划策略如何展现出其独特的优势。
二、动态规划与贪心算法的概述2.1 动态规划动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。
它的核心思想是将问题分解为更小的子问题，并将这些子问题的解决方案存储起来，以便在解决更大的问题时重用。
2.2 贪心算法贪心算法在每一步都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优。
虽然这种策略并不总是能得到全局最优解，但在许多情况下，它能够快速地找到问题的满意解。
三、基于贪心算法的动态规划策略3.1 策略介绍基于贪心算法的动态规划策略结合了动态规划和贪心算法的优点。
在问题的解决过程中，我们首先使用贪心策略来快速找到一个局部最优解，然后利用动态规划的思想来优化这个解。
这样既能保证解的质量，又能提高问题的解决效率。
3.2 策略实施步骤（1）问题分解：首先将问题分解为一系列子问题。
（2）局部最优解：然后使用贪心策略来找到每个子问题的局部最优解。
这一步的关键是在每一步都选择当前状态下的最好选择。
（3）动态规划优化：接着使用动态规划的思想来优化这些局部最优解，形成全局的最优解。
这包括利用已解决的子问题的解决方案，避免重复计算。
（4）解决方案验证与调整：最后，验证解决方案的正确性，并根据需要进行调整。
四、应用实例以旅行商问题（TSP）为例，我们可以使用基于贪心算法的动态规划策略来寻找最短路径。
首先，我们使用贪心策略选择当前状态下的最好路径（如最近邻策略），然后使用动态规划来优化这个路径，通过比较不同路径的组合来找到最短路径。
贪心算法小论文最快还原魔方问题描述将任意打乱三阶魔方还原所需要的最少步数被称为“上帝之数”。
2010年7月，美国加利福尼亚州科学家近日利用计算机破解了这一谜团，研究人员证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20。
魔方术语：SUB-X：意思就是少于的意思，在这就是“在X秒以下”之意比如某高手说sub15秒，就是说，他的平均复原时间在15秒内,或者说,他大多数情况下成绩都在15秒内.设有n个被打乱不同阶魔方同时等待还原。
魔方i需要的还原时间为ti, 1<=i <= n 。
应如何安排n个魔方的还原次序才能使平均SUB时间最小?输入第一行是正整数n，表示有n 个魔方。
接下来的1行中，有n个正整数，表示n个魔方需要的还原时间。
输出计算出SUB。
样例输入1056 4877 44300445 33 689233436样例输出532.00源代码#include<iostream>#include<vector>#include<algorithm>using namespace std;double greedy(vector<int>x);int main(){vector<int>x(10);x.push_back(56);x.push_back(48);x.push_back(77);x.push_back(44);x.push_back(300);x.push_back(445);x.push_back(33);x.push_back(689);x.push_back(2334);x.push_back(36);cout<<"SUB "<<greedy(x)<<endl;return 0;}double greedy(vector<int>x){int n = x.size();sort(x.begin(),x.end());int i=1;for(i=1;i<n;i++){x[i]+=x[i-1];}double t=0;for(i=0;i<n;i++)t+=x[i];t/=n;return t;}贪心算法可以找到令你满意的解答，但不一定是最优的解答。
贪心算法总结什么是贪心算法？贪心算法（Greedy Algorithm）是一种用于求解优化问题的常见算法，其核心思想是在每一步都选择当前最优解，希望最终能够得到全局最优解。
贪心算法在每一步仅考虑局部最优，而不关心全局最优，因此它的计算速度较快。
然而，由于贪心算法没有考虑全局，在某些情况下可能无法得到最优解。
贪心算法并不适用于所有的问题，只适用于一些特殊的问题，例如背包问题、最小生成树问题等。
在实际应用中，需要根据具体问题的特点来判断是否可以使用贪心算法来解决。
贪心算法的基本思路贪心算法的基本思路可以概括为以下几步：1.确定最优解的性质：首先要确定在每一步选择中，能够得到局部最优解。
2.构造贪心选择：根据最优解的性质，每一步都做出一个贪心选择，选择能够获得当前最大或最小收益的方案。
3.确定限制条件：确定问题的限制条件，包括物品的容量、时间限制等。
4.根据限制条件，进行剪枝策略：如果某种选择在限制条件下无法满足要求，则需要进行剪枝，排除该选择。
5.循环执行贪心选择，直到问题得到解决。
贪心算法的优缺点贪心算法具有以下优点：•计算速度快：贪心算法在每一步只考虑局部最优解，不需要对全局进行搜索，因此计算速度较快。
•算法思路简单：贪心算法的思路相对简单，易于理解和实现。
•适用范围广：贪心算法适用于一些特殊问题，如最短路径、最小生成树等。
然而，贪心算法也存在一些缺点：•可能无法得到最优解：由于贪心算法仅考虑局部最优解，而不关心全局最优解，因此可能无法得到最优解。
•需要满足贪心选择性质：贪心算法要求问题具有贪心选择性质，即每一步都能够得到局部最优解。
如果问题不具备这个性质，贪心算法可能不适用。
贪心算法的应用场景贪心算法适用于一些特殊的问题，以下是一些常见的应用场景：1. 最短路径问题最短路径问题是指在一个加权有向图中，找出从一个顶点到另一个顶点的最短路径。
贪心算法可以用来解决一些简单的最短路径问题，如Dijkstra算法。
贪心算法实验小结
最近，我和我的同学们在实验室里进行了一次关于贪心算法的实验，探究贪心算法在旅行商问题中的应用。
实验的准备工作非常简单，我们只需要准备好实验所需的数据，并将其输入到计算机中即可。
之后，我们使用贪心算法来解决这个旅行商问题，运用贪心思想，在遍历所有城市时，选择当前停留时间最短的城市作为下一站，以期最终获得最短的旅行路线。
实验的过程中，我们发现，贪心算法可以有效地解决旅行商问题，即使在城市数量较多的情况下，它仍然能够在较短的时间内得到最优解。
除了旅行商问题之外，贪心算法还可以应用于其他许多其他问题，比如背包问题，最大化问题等。
在这次实验中，我们研究到了贪心算法的原理和应用，对于贪心算法在求解复杂问题中的重要性有了更深的认识。
此外，我们也体会到了贪心算法的局限性，它只能获得局部最优解，而不能保证全局最优解。
总之，本次实验对我们的研究有很大的帮助，不仅加深了对贪心算法的认识，而且还能够更好地理解其在实际问题中的应用，让我们更加清楚如何有效地利用贪心算法来解决复杂问题。
贪⼼算法总结简介贪⼼算法（英⽂：greedy algorithm），是⽤计算机来模拟⼀个“贪⼼”的⼈做出决策的过程。
这个⼈⼗分贪婪，每⼀步⾏动总是按某种指标选取最优的操作。
⽽且他⽬光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想⽽知，并不是所有的时候贪⼼法都能获得最优解，所以⼀般使⽤贪⼼法的时候，都要确保⾃⼰能证明其正确性。
本⽂主要介绍，在解决诸多贪⼼算法的问题之后的⼼得。
常⽤场景最常见的贪⼼算法分为两种。
「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从⼩到⼤）选择。
」。
「我们每次都取 XXX 中最⼤/⼩的东西，并更新 XXX。
」（有时「XXX 中最⼤/⼩的东西」可以优化，⽐如⽤优先队列维护）第⼀种是离线的，先处理后选择，第⼆种是在线的，边处理边选择。
常见的出题背景为:确定某种最优组合（硬币问题）区间问题（合理安排区间）字典序问题最值问题A最优组合硬币问题是贪⼼算法⾮常经典的题⽬，关于最优组合问题，我认为主要分为两种类型:简单 -- 直接排序之后按照某种策略选取即可复杂 -- 除了按照贪⼼策略外，还需要进⾏某些处理或者模拟硬币问题硬币问题有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。
现在要⽤这些硬币来⽀付A元，最少需要多少枚硬币？假设本题⾄少存在⼀种⽀付⽅法。
0≤C1、C5、C10、C50、C100、C500≤1090≤A≤109本题是上述说的简单类型的题⽬，简⽽⾔之要使得硬币最少，则优先使⽤⼤⾯额的硬币。
因此本题的解法便⾮常清晰了，只需要从后往前遍历⼀遍即可（默认为硬币已经按⾯额⼤⼩进⾏排序）const int V[6] = {1, 5, 10, 50, 100, 500};int A, C[6]; // inputvoid solve(){int ans(0);for (int i = 5; i >= 0; -- i){int t = min(A / V[i], C[i]);A -= t * V[i];ans += t;}cout << ans << '\n';}零花钱问题POJ3040 AllowanceDescriptionAs a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like topay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.Input* Line 1: Two space-separated integers: N and C* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.Output* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowanceSample Input3 610 11 1005 120Sample Output111这题的题⽬⼤意是:农场主每天都要给贝西⾄少为C的津贴。
贪心算法求解汽车加油问题1 引言随着科学的发展，人们生活中面临的大数据量越来越多。
生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展，线性规划、动态规划、贪心策略等一系列运筹学模型越来越多被应用到计算机算法学中。
当一个问题具有最优子结构性质和贪心选择性质时，可用动态规划法来解决。
但是贪心算法通常会给出一个更简单、直观和高效的解法。
贪心算法通过一系列的选择来得到一个问题的解。
尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效[1]。
2 贪心算法2.1 贪心算法概述贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。
贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。
也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。
贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。
用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。
贪婪算法是一种改进了的分级处理方法。
其核心是根据题意选取一种量度标准。
然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。
这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。
初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。
因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。
最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。
每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
2.2 贪心算法的基本要素贪心算法通过一系列的选择得到问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。
但是对于一个问题，怎么知道是否可以用贪心算法解决此问题，以及能否得到问题的最优解呢？这个问题难以给予肯定的回答。
但是，我们从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性和最优子结构性质。
贪心选择性是指所求问题的整体最优解可以通过一系列局部最优的选择得到。
因此，对于一个具体问题，它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终可以得到整体最优的结果，即通过贪心选择后，原问题被简化为规模更小的类似子问题。
而最优子结构性质，主要是指原问题的最优解包含子问题的最优解。
2.3 贪心算法的特性通过对比能够用贪心算法解决的诸多问题，我们不难总结出贪心算法能够解决的问题的一系列特性：（1）存在一个最优的方法来解决的问题。
为了构造问题的解决方案,有一个候选的对象是一个集合：比如不同面值的硬币。
（2）随着算法的进行，将产生两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但是被丢弃的候选对象。
（3）算法中将产生一个用来检查一个候选对象是否提供了问题的解答的函数。
当然，该函数并不考虑此时的解决方法是否最优。
（4）算中法另一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。
和上一个函数一样,此时不考虑解决方法的最优性。
（5）选择函数指出哪一个剩余的候选对象可能构成问题的解。
（6）最后返回解的值。
为了解决原问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,使得贪婪算法一步一步的进行。
起初,算法选出的候选对象的集合为空，接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象，然后加入到一个集合中，如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑。
每一次都扩充集合，并检查该集合是否构成解。
如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
2.4 贪心算法的基本思路用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。
当某个算法中的某一步不能再继续前进时，算法停止。
贪心算法思想的本质就是分治，或者说：分治是贪心的基础。
每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。
利用贪心策略解题，需要解决两个问题：（1）该题是否适合于用贪心策略求解；（2）如何选择贪心标准，以得到问题的最优/较优解。
具体的实现过程如下：（1）建立数学模型来描述问题。
（2）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题。
（3）对每一子问题求解，得到子问题的局部最优解。
（4）把子问题的解局部最优解合成原来解问题的一个解。
实现的算法的过程如下：从问题的某一初始解出发；while（能朝给定总目标前进一步）do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。
3 经典例子分析3.1 0-1背包问题0-1背包问题：给定n种物品和一个背包。
物品i的重量和价值分别是w i和v i，背包的容量为C。
要求正确的选取装入背包的物品，使得装入背包的物品价值之和最大。
例如：C=30物品：A B C重量：28 12 12价值：30 20 20根据贪心选择策略，首先选择A，然后再比较B、C，无法再装入。
可以看出，最终的结果是将A装入背包中。
但是，如不按贪心算法求解，实际是装入B和C最好。
因此，对于0-1背包问题，贪心选择不能达到结果最优，这是因为在这种情况下，无法保证最终将背包装满，部分闲置的空间使得每公斤背包的价值下降了。
因此，在考虑此类的背包问题时，应该比较选择该物品呵不选择该物品所导致的最终方案，然后再做出最好的选择，此时可用动态规划算法求解。
显然，对于以上例子，如果不要求选择物品的全部装入背包，允许我们只选择部分装入背包，此问题及转化为普通背包问题。
此时即可用贪心选择算法求解。
一般步骤为：首先选择将每公斤价值最大的物品装入背包，如果背包未满，再选择每公斤价值次大的物品装入，以此类推。
3.2 加油站问题（习题4-16）（一）问题描述一辆汽车加满油后可行驶N公里。
旅途中有若干个加油点。
设计一个有效算法，指出应在哪些加油站加油，使得旅途中加油次数最少，并证明算法能产生一个最优解。
（二）问题分析设汽车在起点已经为加满油的状态，记加油的次数为k，起点与终点距离为S，加油站的个数为n，加油站i与加油站i+1之间的距离存放在一个数组a[i]中（i=0、1、2、3…..n），其中a[0]表示汽车位于起始点,a[n+1]表示汽车到达终点。
对于原问题，主要有以下几种情况：A 当S<N或S=N时，无需加油，即k=0；B 当S>N时：（1）各加油站之间的距离相等且等于N，即a[i]=N，需要加油次数至少为k=n；（2）各加油站之间的距离相等且大于N，即a[i]>N，则不可能到达终点。
（3）各加油站之间的距离相等且小于N，即a[i]<N，则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；（4）各加油站之间的距离不相等，即a[i]!=a[j]，则加油次数k可以通过以下算法得到。
具体算法描述如下：int add(int b[ ],int m,int n){ //求一个从m到n的数列的和int sb;for(int i=m;i<n;i++) sb+=b[i];return sb; }int Tanxin(int a[n], int N) //a[n]表示加油站的个数，N为加满油能行驶的最远距离{int b[n]; //若在a[i]加油站加油，则b[i]为1，否则为0int m=0;if(a[i]>N) return ERROR; //如果某相邻的两个加油站间的距离大于N，则不能到达终点if(add(a[i], 0, n)<N){ //如果这段距离小于N，则不需要加油b[i]=0;return add(b[i],0,n);}if(a[i]==a[j]&&a[i]==N){ //如果每相邻的两个加油站间的距离都是N，则每个加油站都需要加油b[i]=1;return add(b[i],0,n);}if(a[i]==a[j]&&a[i]<N){ //如果每相邻的两个加油站间的距离相等且都小于Nif( add(a[i],m,k) < N && add(a[i],m,k+1) > N ){b[k]=1;m+=k;}return add(b[i],0,n);}if(a[i]!=a[j]){ //如果每相邻的两个加油站间的距离不相等且都小于Nif( add(a[i],m,k) < N && add(a[i],m,k+1) > N ){b[k]=1;m+=k;}return add(b[i],0,n);}viod main( ){int a[ ];scanf("%d",a);scanf("/n");scanf("/d",&N);Tanxin(a[ ],0,n);}由于贪心算法适用的问题必须满足连个属性：贪心性质和最优子结构，因此，对于该汽车加油的问题是否适合用贪心算法，要先判定其是否具有这两个性质。
●贪心选择性质对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。
