当前位置：文档之家 › 贪心法的思想方法及证明

贪心法的思想方法及证明

  • 格式：docx
  • 大小：17.16 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

贪心PPT课件

贪心PPT课件
方法如下：先将单位块收益按从大到小进行排列，然后 用循环从单位块收益最大的取起，直到不能取为止便得到了 最优解。
【问题2】0/1背包问题
给定一个最大载重量为M的卡车和N种动物。已知第i种动 物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整 数，编程确定一个装货方案，使得装入卡车中的所有动物 总价值最大。
给定一个最大载重量为M的卡车和N种食品，有食盐，白 糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品 价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车 中的所有物品总价值最大。
【分析】因为每一个物品都可以分割成单位块，单位块的利 益越大，显然总收益越大，所以它局部最优满足全局最优， 可以用贪心法解答。
6 5 3 7 1 9 10 【样例输出】 90
【思路点拨】假设取水的人按照1...n的顺序排列的，那么问题就转 化为求以下公式的最小值：
Total=T1+(T1+T2)+(T1+T2+T3)+...+(T1+T2+...+Tn)，对公式换个 写法：
Total=nT1+(n-1)T2+(n-2)T3...+2Tn-1+Tn 现在你是否发现一点什么呢？
【分析】按贪心法：每次选价格最大的装载。很明显有反例： 设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别 是40,50,70,其对应的总价值分别是80、100、150。
三、贪心策略与其他算法的区别
1.贪心与递推：与递推不同的是，贪心法中推进的每一步 不是依据某一固定的递推式，而是当前看似最佳的贪心决 策，不断的将问题归纳为更加小的相似的子问题。所以归 纳、分析、选择正确合适的贪心策略，是正确解决贪心问 题的关键。

如何证明贪心算法的正确性

如何证明贪心算法的正确性

如何证明贪⼼算法的正确性
在使⽤贪⼼算法时，我们常常会通过直觉来得出贪⼼策略。

可是，我们要如何来证明贪⼼策略的正确性呢?
贪⼼算法解决的问题常常可以划分成多个⼦过程，我们对每个⼦过程采⽤相同的贪⼼策略可以实现全局的最优。

这也是贪⼼算法与动态规划算法的区别——动态规划算法对于每个⼦过程选取相同的贪⼼策略⽆法实现全局的最优。

当我们得到贪⼼策略时，我们很⾃然地会想到使⽤⼀种较暴⼒的⽅法，即证明对于每个⼦过程使⽤贪⼼策略能够实现全局最优。

具体地，我们如何使⽤这种⽅法来证明贪⼼策略的正确性呢？我们常常是通过交换任意两个⼦过程然后证明交换后⽆法实现全局的更优来证明，这其实是反证法的应⽤，我们通过改变贪⼼策略然后证明改变后⽆法实现全局的更优从⽽来证明贪⼼策略的正确性。

另⼀⽅⾯，我们也可以使⽤类似于数学归纳法的⽅法来证明贪⼼策略的正确性。

我们⾸先可以证明对于⼀个初始的⼦过程实现贪⼼策略能够实现该⼦过程的最优。

然后假设对于前n个⼦过程使⽤贪⼼策略能够实现前n个⼦过程的最优，通过该假设来证明前n+1个⼦过程使⽤贪⼼策略也能够实现最优，这样贪⼼策略的正确性便得以证明。

这就是贪⼼算法常⽤的证明⽅法。

关于贪心算法的正确性证明

关于贪心算法的正确性证明

“贪心选择性质”的证明下面用数学归纳法给出一个简单的证明。

我们对算法所做的选择步数进行归纳，证明对任意正整数k，算法的前k步选择都能导致一个最优解.定理算法Select执行到第k步，选择k项活动=1，,…,那么存在最优解A包含=1，,…。

证将S中的活动按照截止时间递增顺序排列.归纳基础：k=1时，算法选择了活动1.我们仅需要证明：存在一个最优解包含了活动1.设A{ ，,…,}是一个最优解，如果i11,那么用1替换，得到A’，即A’=(A-{ })｛1｝那么A’和A的活动个数相等。

且活动1比i1结束的更早，因此和，,…,等活动都相容。

于是A’也是问题的一个最优解.归纳步骤：假设对于任意正整数k，命题正确.令=1，,…是算法前k 步顺序选择的活动，那么存在一个最优解A=｛=1，,…｝B如果令S’是S中剩下的与i1，i2,…，ik相容的活动，即S’=｛j|, j S｝那么B是S’的一个最优解，如若不然，假如S’有解B’，| B’|>|B|,那么用B’替换B以后得到的解｛=1，,…｝B’将比A的活动更多，与A是最优解矛盾.根据对归纳基础的证明，算法第一步选择结束时间最早的活动总是导致一个最优解，故对子问题S’存在一个最优解B*=｛,…｝.由于B*与B都是S’的最优解，因此| B*|=|B|.于是A’={ =1，,…} B*=｛=1，,…,｝(B*-{ ik+1})与A的活动数目一样多，也是一个最优解，而且恰好包含了算法前k+1步选择的活动。

根据归纳法命题得证.定理告诉我们，算法前k步的选择都将导致最优解，其中k=1，2，….因为至多有n项活动，被选择的活动个数不会超过n，因此算法至少在n步内结束，结束时得到的就是问题的最优解.例有集装箱1,2,…,n准备装上轮船。

其中集装箱i的重量是C,且对集装箱无体积限制。

问如何选择而使得装上船的集装箱个数最多设=1表示第i个集装箱可以装上船，否则=0，则这个问题可以描述为：maxC=0,1 i=1,2,…,n这是一个整数规划问题，也是0-1背包问题的特殊情况.对于0-1背包问题可以使用动态规划算法求解.但是对于这个问题有更好的算法——贪心法.贪心选择策略非常简单，就是“轻者先装”，直到再装任何集装箱将使轮船载重量超过C是停止.算法 Loading输入：集装箱集合N=｛1,2,…,n｝，集装箱i的重量 ,i=1,2,…,n输出：I N,准备装入船的集装箱集合1.对集装箱重量排序，使得2.I{1}3.W4.for j 2 to n do5. if W + C6. Then W W+7. I I{j}8. else return I,W算法的时间主要是行1的排序时间O(nlogn),行4的for循环总计执行O(n)时间，于是算法的时间复杂度是O(nlogn)。

贪心算法的局部最优性

贪心算法的局部最优性

贪心算法的局部最优性贪心算法是一种常用且有效的算法设计策略。

它的核心思想是在解决问题的每个阶段，都选择当前情况下最优的局部解，希望最终能够得到全局最优解。

贪心算法在很多实际问题中都有应用，其成功与否与问题的性质和贪心策略的选择密切相关。

一、贪心算法的基本思想贪心算法的基本思想是通过不断地做出局部最优选择来达到全局最优。

贪心算法在每个阶段都做出一个局部最优选择，然后通过这些局部最优选择逐步构建一个全局最优解。

二、贪心算法的局部最优性证明贪心算法能够得到局部最优解的前提是：每一步的局部最优解能够推导出全局最优解。

下面将从数学的角度证明贪心算法的局部最优性。

设问题的最优解为S，贪心算法得到的局部最优解为A。

假设A不是S的最优解，那么存在一个更优解B，使得B更优于A。

但是由于贪心算法的策略是选择当前情况下的局部最优解，所以A必然是在B之前被选择的。

换句话说，贪心算法在每个阶段选择的最优解都是局部最优的。

接下来，我们可以将最优解S划分成两部分：一部分是已经选择的解A和其它局部最优解的组合，另一部分是在贪心算法之后还没有选择的解。

假设在每个阶段选择局部最优解并不能得到全局最优解，那么就存在一种选择策略，使得在贪心算法之后仍然可以得到一个与S不同的更优解。

然而，这与贪心算法选择了局部最优解的原则相矛盾。

因此，我们可以得出结论：贪心算法的局部最优解能够推导出全局最优解，即贪心算法具有局部最优性。

三、贪心算法的应用举例1. 零钱兑换问题假设有不同面额的硬币，例如1元、2元、5元，现要兑换总金额为N的零钱。

如果使用贪心算法，每次都选择面额最大的硬币进行兑换，直到兑换完毕。

这样所需硬币的数量最少。

2. 区间覆盖问题给定一个区间集合，选取尽可能少的区间，使得这些区间的并集包含了所有的区间。

贪心算法可以选择尽可能早结束的区间进行覆盖，从而得到最优解。

3. 背包问题背包问题分为01背包和完全背包。

在01背包问题中，每个物品只有一个，可以选择放或者不放。

贪心算法 实验报告

贪心算法 实验报告

贪心算法实验报告贪心算法实验报告引言：贪心算法是一种常用的算法设计策略，它通常用于求解最优化问题。

贪心算法的核心思想是在每一步选择中都选择当前最优的解，从而希望最终能够得到全局最优解。

本实验旨在通过实际案例的研究，探索贪心算法的应用和效果。

一、贪心算法的基本原理贪心算法的基本原理是每一步都选择当前最优解，而不考虑整体的最优解。

这种贪婪的选择策略通常是基于局部最优性的假设，即当前的选择对于后续步骤的选择没有影响。

贪心算法的优点是简单高效，但也存在一定的局限性。

二、实验案例：零钱兑换问题在本实验中，我们以零钱兑换问题为例，来说明贪心算法的应用。

问题描述：假设有不同面值的硬币，如1元、5元、10元、50元和100元，现在需要支付给客户x元，如何用最少的硬币数完成支付？解决思路：贪心算法可以通过每次选择当前面值最大的硬币来求解。

具体步骤如下：1. 初始化一个空的硬币集合，用于存放选出的硬币。

2. 从面值最大的硬币开始，如果当前硬币的面值小于等于待支付金额，则将该硬币放入集合中，并将待支付金额减去该硬币的面值。

3. 重复步骤2，直到待支付金额为0。

实验过程：以支付金额为36元为例，我们可以通过贪心算法求解最少硬币数。

首先，面值最大的硬币为100元，但36元不足以支付100元硬币，因此我们选择50元硬币。

此时，剩余待支付金额为36-50=-14元。

接下来，面值最大的硬币为50元，但待支付金额为负数，因此我们选择下一个面值最大的硬币，即10元硬币。

此时，剩余待支付金额为-14-10=-24元。

继续选择10元硬币，剩余待支付金额为-24-10=-34元。

再次选择10元硬币，剩余待支付金额为-34-10=-44元。

最后，选择5元硬币，剩余待支付金额为-44-5=-49元。

由于待支付金额已经为负数，我们无法继续选择硬币。

此时，集合中的硬币数为1个50元和3个10元，总共4个硬币。

实验结果：通过贪心算法，我们得到了36元支付所需的最少硬币数为4个。

第5章 贪心法

第5章 贪心法

5.1 引言
三、背包问题
1．背包问题 给定一个承重量为C的背包，n个重量分别为 w1,w2,…,wn的物品。已知物品i放入背包能产生vi的价 值（放入单位重量的物品i，产生的价值为vi/wi）， i=1,2,…,n。如何装包才能获得最大价值？ 实际上，就是要求找到一组非负且不超过1的实数
x1,x2,…,xn满足∑xiwi≤C，且使得∑xivi达到最大值。
三、背包问题
Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break;
5.1 引言
算法knapsack的 主要计算时间在于将 各种物品依其单位重 量的价值从大到小排 序。因此，算法的计 算时间上界为 O（nlogn）。 为了证明算法的正确 性，还必须证明背包 问题具有贪心选择性 质。
5.1 引言
三、背包问题
3．求解思想 贪心准则2——根据物品的重量由小到大来放。
从剩下的物品中选择可装入背包的重量最小的物品。 虽然这种规则对于前面的例子能产生最优解，但在一般 情况下则不一定能得到最优解。 （由上面实例可知，它不是最优贪心准则）
5.1 引言
三、背包问题
3．求解思想 贪心准则3——根据价值/重量（即单位价值）由大 到小来放。 每一项计算yi=vi/Wi,即该项值和大小的比，再按 比值的降序来排序，从第一项开始装背包，然后是第二 项，依次类推。尽可能的多放，直到装满背包。 （可以证明它是最优贪心准则）
5.2单源最短路问题
五、Dijkstra算法
算法中图使用邻接表表示，其示意图如下。

贪心策略

贪心策略

基本思路
初看这一问题，很容易想到用贪心策略来求解， 即选择集合中最大的可以删除的数开始删起，直 到不能再删除为止，而且通过一些简单的例子来 验证，这一贪心标准似乎也是正确的，例如，当 m=2 ， n=10 时 ， 集 合 P ＝ {2,3,…,10} ， 运 用 上 述 “贪心标准”可以得到这一问题的正确的最优解 d=5＋4＋3＝12，即其d-规则过程如下： 1. a=5 P={2,3,4,6,7,8,9} d=5 2. a=4 P={2,3,6,7,9} d=5+4=9 3. a=3 p={2,7} d=5+4+3=12
算法
问题初始化； 问题初始化； 按Vi从大到小将商品排序； 从大到小将商品排序；
{读入数据}
I := 1; repeat if M = 0 then Break; {如果卡车满载则跳出循环} M := M - Wi; if M >= 0 then 将第I种商品全部装入卡车 else 将(M + Wi)重量的物品I装入卡车; I := I + 1; {选择下一种商品} until (M <= 0) OR (I >= N)
算法
I := 1 {汽车出发设定为第1个加油站} L := C*D2； {油箱装满油能行驶的距离} repeat 在L距离以内，向后找第一个油价比I站便宜的加油站J； if J存在 then if I站剩余油能到达J then 计算到达J站的剩油 else 在I站购买油，使汽车恰好能到达J站 else 在I站加满油； I := J； {汽车到达J站} until 汽车到达终点；
分析
但是，如果再仔细地分析一个例子， m=3， 但是，如果再仔细地分析一个例子，当m=3，n＝ 18时 如果还是使用上述“贪心标准” 18时，如果还是使用上述“贪心标准”，则得到 问题的d 规则总分为d=35 d=35， 问题的d-规则总分为d=35，其d-规则序列为 9,8,7,6,5），而实际上可以得到最大d ），而实际上可以得到最大 （9,8,7,6,5），而实际上可以得到最大d-规则总 分为d 38，其对应的d 分为d＝38，其对应的d-规则序列为 9,8,7,6,3,5）。 （9,8,7,6,3,5）。 为什么会出现这样的反例呢？ 为什么会出现这样的反例呢？ 这是因为，问题中要使得d 规则总分d值越大， 这是因为，问题中要使得d-规则总分d值越大， 不光是要求每一个d分值越大越好， 不光是要求每一个d分值越大越好，也要求取得 分值越多越好。 的d分值越多越好。 因此，本题不能采用上述的贪心策略求解 求解。 因此，本题不能采用上述的贪心策略求解。

贪心法

贪心法

贪心法贪心法(Greedy Approach)又称贪婪法, 在对问题求解时，总是做出在当前看来是最好的选择，或者说是：总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

如单源最短路经问题，最小生成树问题等。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心法的设计思想当一个问题具有以下的性质时可以用贪心算法求解:每一步的局部最优解，同事也说整个问题的最优解。

如果一个问题可以用贪心算法解决，那么贪心通常是解决这个问题的最好的方法。

贪婪算法一般比其他方法例如动态规划更有效。

但是贪婪算法不能总是被应用。

例如，部分背包问题可以使用贪心解决，但是不能解决0-1背包问题。

贪婪算法有时也用用来得到一个近似优化问题。

例如，旅行商问题是一个NP难问题。

贪婪选择这个问题是选择最近的并且从当前城市每一步。

这个解决方案并不总是产生最好的最优解，但可以用来得到一个近似最优解。

让我们考虑一下任务选择的贪婪算法的问题, 作为我们的第一个例子。

问题：给出n个任务和每个任务的开始和结束时间。

找出可以完成的任务的最大数量，在同一时刻只能做一个任务。

例子:下面的6个任务：start[] = {1, 3, 0, 5, 8, 5};finish[] = {2, 4, 6, 7, 9, 9};最多可完成的任务是：{0, 1, 3, 4}贪婪的选择是总是选择下一个任务的完成时间至少在剩下的任务和开始时间大于或等于以前选择任务的完成时间。

我们可以根据他们的任务完成时间，以便我们总是认为下一个任务是最小完成时间的任务。

1)按照完成时间对任务排序2)选择第一个任务排序数组元素和打印。

3) 继续以下剩余的任务排序数组。

……a)如果这一任务的开始时间大于先前选择任务的完成时间然后选择这个任务和打印。

贪心策略

贪心策略
可通过局部的贪心选择来达到问题的全局最优解。 运用贪心策略解题，一般来说需要一步步的进行 多次的贪心选择。在经过一次贪心选择之后，原 问题将变成一个相似的，但规模更小的问题，而 后的每一步都是当前看似最佳的选择，且每一个 选择都仅做一次。
原问题的最优解包含子问题的最优解，即问题具 有最优子结构的性质。
取数游戏
给出2n（n<=100）个自然数（数小于等于30000）。游戏双方分 别为A 方（计算机方）和B方（对奕的人）。只允许从数列两头取 数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和 最大为取胜方；若双方和相等，属于A胜。试问A方可否有必胜的 策略？
输入：键盘输入n及2*n个自然数。 输出：共3n+2行，其中前3*n行为游戏经过。每3行分别为A方所取的
数和B方所取的数，及B方取数前应给予的适当提示，让游戏者选 择取哪一头的数（L/R——左端或右端）。最后2行分别为A方取得 的数和与B方取得的数和。 输入样例： ４ 79364253
问题分析
设n=4，自然数列为：7 9 3 6 4 2 5 ห้องสมุดไป่ตู้ 。我们设计一种原始 的贪心策略，让A每次取数列两头较大的那个数，则游戏者也不会傻， 他也会这么干，所以在上面的数列中，A方会顺序取7、3、4、5,B方 会顺序取9、6、2、3,由此得出：A方取得的数和为7+3+4+5＝19,B方 取得的数和为9+6+2+3＝20,按照规则，判定A输。
实现该算法的过程： 从问题的某一初始解出发； While 能朝给定总目标前进一步 do
求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解
引例
在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的 总共N个数的和最大。

贪心算法的原理是

贪心算法的原理是

贪心算法的原理是
贪心算法是一种求解最优问题的常用算法思想，其基本原理是在每一步选择中都采取当前状态下最优的选择，从而希望最终得到全局最优解。

贪心算法的主要特点是局部最优策略同时也是全局最优策略。

贪心算法通常包含以下步骤：
1. 确定问题的最优子结构：即问题的整体最优解可以通过一系列局部最优解来达到。

这是贪心算法的基础，也是保证贪心选择性质的关键。

2. 构造贪心选择：通过局部最优策略来构造每一步的最优解，不考虑前面步骤的选择是否能够达到全局最优。

3. 解决子问题：将子问题缩小，通过递归或迭代的方式求解。

4. 合并子问题的解：将子问题的解合并起来，形成原问题的解。

贪心算法的正确性依赖于贪心选择性质和最优子结构性质。

贪心选择性质指的是，通过局部最优解就可以推导出全局最优解。

最优子结构性质指的是，问题的整体最优解可以通过一系列局部最优解来达到。

贪心算法的应用广泛，常见的问题包括：
1. 找零钱问题：给定一些面额不同的硬币和一个总金额，如何用最少数量的硬币凑出总金额。

2. 区间调度问题：给定一些活动的开始时间和结束时间，如何安排活动使得参加的活动数量最多。

3. Huffman编码问题：如何用最短的编码长度来表示一个给定概率分布的字符集。

虽然贪心算法通常能够在很短的时间内找到一个解，但并不是所有问题都适合使用贪心算法。

贪心算法不能保证得到最优解，只能保证得到一个近似最优解。

因此，在使用贪心算法解决问题时需要根据具体问题的特性来判断是否适合使用贪心算法。

贪心算法基本思想和典型例题（转）

贪心算法基本思想和典型例题（转）

贪⼼算法基本思想和典型例题（转）贪⼼算法⼀、算法思想贪⼼法的基本思路：——从问题的某⼀个初始解出发逐步逼近给定的⽬标，以尽可能快的地求得更好的解。

当达到某算法中的某⼀步不能再继续前进时，算法停⽌。

该算法存在问题：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）每次选取单位容量价值最⼤的物品，成为解本题的策略。

实现这个算法是学习算法分析与设计这门课程的需要。

贪⼼算法是所接触到的第⼀类算法。

算法从局部的最优出发，简单⽽快捷。

对于⼀个问题的最优解只能⽤穷举法得到时，⽤贪⼼法是寻找问题次优解的较好算法。

贪⼼法是⼀种改进了的分级处理⽅法。

⽤贪⼼法设计算法的特点是⼀步⼀步地进⾏，根据某个优化测度（可能是⽬标函数，也可能不是⽬标函数），每⼀步上都要保证能获得局部最优解。

每⼀步只考虑⼀个数据，它的选取应满⾜局部优化条件。

若下⼀个数据与部分最优解连在⼀起不再是可⾏解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为⽌。

这种能够得到某种度量意义下的最优解的分级处理⽅法称为贪⼼法。

选择能产⽣问题最优解的最优度量标准是使⽤贪⼼法的核⼼问题。

贪心算法的基本思路

贪心算法的基本思路

贪心算法的基本思路
以下是贪心算法的基本思路：
1. 定义问题：明确要解决的问题和可用的操作。

2. 选择最优解：在每一步中，选择当前看起来最优的解决方案。

这个选择通常基于问题的局部信息和贪心准则。

3. 局部最优：根据贪心准则做出的选择应该在当前步骤是最优的，即能够获得最大或最小的效益。

4. 构建解决方案：通过一系列的局部最优选择，逐步构建出整个问题的解决方案。

5. 检查可行性：在每一步之后，检查所做出的选择是否满足问题的约束条件和限制。

6. 重复步骤：重复上述步骤，直到达到问题的终止条件或无法进一步做出改进。

贪心算法通常在每一步都做出局部最优选择，希望通过一系列局部最优选择来达到全局最优解。

然而，贪心算法并不保证一定能得到全局最优解，尤其是在复杂的问题中。

贪心算法的优势在于其简单性和效率。

它通常在每一步只需要考虑少量的因素，因此计算复杂度较低。

贪心算法在一些情况下可以提供较好的近似解，并且在实际应用中经常被使用。

需要注意的是，贪心算法的正确性和有效性取决于问题的特性和贪心准则的选择。

在使用贪心算法时，需要仔细分析问题，选择合适的贪心准则，并通过实例验证算法的正确性。

贪心策略

贪心策略

• 【引例】在一个N×M的方格阵中，每一格子赋予一个数 （即为权），规定每次移动时只能向上或向右。现试找出 一条路径，使其从左下角至右上角所经过的权之和最大。 • 我们以2×3的矩阵为例：
若按贪心策略求解，所得路径为：1→3→4→6； 若按动态规划求解，所得路径为：1→2→10→6。
贪心法的特点
【算法实现】首先按照b1<=b2<=…<=bn的顺序排序，依次 考虑各个活动，如果没有和已经选择的活动冲突，就选； 否则就不选。 贪心策略：取第一个区间； 【正确性】：如果不选b1，假设第一个选择的是bi，则如 果bi和b1不交叉则多选一个b1更划算；如果交叉则把bi换 成b1不影响后续选择。
例题5：活动安排
2、区间选点问题
• 给定n个闭区间[ai, bi]，在数轴上选尽量少的点， 使得每个区间内都至少有一个点（不同区间内含 的点可以是同一个）。
【算法】：首先按照b1<=b2<=…<=bn排序。每次标记当前 区间的右端点X，并右移当前区间指针，直到当前区间不包 含X，再重复上述操作。 贪心策略：取最后一个。
• 设有n个活动的集合E={1,2,..,n}，其中每个活动 都要求使用同一资源，如演讲会场等，而在同一 时间内只有一个活动能使用这一资源。每个活动i 都有一个要求使用该资源的起始时间si和一个结 束时间fi，且si<fi。如果选择了活动i，则它在半 开时间区间[si,fi)内占用资源。若区间[si,fi)与区 间[sj,fj)不相交，则称活动i与活动j是相容的。也 就是说，当fi>=sj或fj>=si时，活动i与活动j相容。 选择出由互相兼容的活动组成的最大集合。
例题2：排队问题
• 在一个食堂，有n个人排队买饭，每个人买 饭需要的时间为Ti，请你找出一种排列次序， 是每个人买饭的时间总和最小。

贪心算法

贪心算法

6.贪心方法模型
a.工程计划模型 b.部分背包与每步最优 c.构造贪心算法
a.工程计划模型
我们常常碰到这样的问题：完成一个工程需
要若干个步骤，每个步骤都有若干种方法， 图示—— 步骤a 步骤b 步骤c ... 步骤n 方法b1 方法c1 方法a1 方法b2 方法c2 方法n1 方法a2 方法b3 方法c3 方法c4

种树问题：一条街道分为n个区域（按1-n编号）， 每个都可种一棵树。有m户居民，每户会要求在区 域i-j区间内种至少一棵树。现求一个能满足所有要 求且种树最少的方案。 算法构造： 1.对于要求，以区间右端（升序）为首要关键字， 左端（升序）为次要关键字排序。 2.按排好的序依次考察这些要求，若未满足，则在 其最右端的区域种树，这时可能会满足多个要求。 证明思路：解法并不唯一，关键是证明没有比该解 法更好的解法。按步骤1排序之后，会发现对于每 个要求，在最右边的区域内种树所得的结果总不会 差于在其他区域种树。至于为什么这样排序，留给 你——读者们思考吧。

每个方法有一个权值（如效率、质量），其大小往 往和其他步骤中选取的方法有关。有些时候权值无 意义，表示方法不可选择。要求给出一个方法组合， 是权值和最大。 在这里，暂且把它称作“工程计划”。很多实际问 题都可以归纳为这个模型。 对于不同形式的工程计划，我们有不同的解法。 若权值与整个过程或前后步骤的方法选择都有关， 我们使用搜索算法——时间复杂度高得吓人。 若每个权值只与上（或下）一步或少数几步的方法 选择都有关，我们使用动态规划——有比较高的效 率，在下一章会讲到。 若每个权值与其他步骤的方法选择都没有关系，我 们使用贪心方法。

算法分析：设a[i]为第I堆纸牌的张数（0<=I<=n）， v为均分后每堆纸牌的张数，s为最小移动次数。 我们用贪心算法，按照从左到右的顺序移动纸牌。 如第I堆的纸牌数不等于平均值，则移动一次（即s 加1），分两种情况移动： 1．若a[i]>v，则将a[i]-v张从第I堆移动到第I+1堆； 2．若a[i]<v，则将v-a[i]张从第I+1堆移动到第I堆。 为了设计的方便，我们把这两种情况统一看作是将 a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v; a[I+1]=a[I+1]+a[i]-v. 在从第I+1堆取出纸牌补充第I堆的过程中可能回出 现第I+1堆的纸牌小于零的情况。

贪心法（一）：贪心法的基本思想

贪心法（一）：贪心法的基本思想

贪⼼法（⼀）：贪⼼法的基本思想在实际问题中，经常会遇到求⼀个问题的可⾏解和最优解的问题，这就是所谓的最优化问题。

每个最优化问题都包含⼀组限制条件和⼀个优化函数，符合条件的解决⽅案称为可⾏解，使优化函数取得最佳值的可⾏解称为最优解。

贪⼼法是求解这类问题的⼀种常⽤算法，它从问题的某⼀个初始解出发，采⽤逐步构造最优解的⽅法向给定的⽬标前进。

贪⼼法在每个局部阶段，都做出⼀个看上去最优的决策（即某种意义下的、或某个标准下的局部最优解），并期望通过每次所做的局部最优选择产⽣出⼀个全局最优解。

做出贪⼼决策的依据称为贪⼼准则（策略）。

想象这样⼀个场景：⼀个⼩孩买了价值少于10元的糖，并将10元钱交给了售货员。

售货员希望⽤数⽬最少的⼈民币（纸币或硬币）找给⼩孩。

假设提供了数⽬不限的⾯值为5元、2元、1元、5⾓以及1⾓的⼈民币。

售货员应该这样找零钱呢？售货员会分步骤组成要找的零钱数，每次加⼊⼀张纸币或⼀枚硬币。

选择要找的⼈民币时所采⽤的准则如下：每⼀次选择应使零钱数尽量增⼤。

为保证不多找，所选择的⼈民币不应使零钱总数超过最终所需的数⽬。

假设需要找给⼩孩6元7⾓，⾸先⼊选的是⼀张5元的纸币，第⼆次⼊选的不能是5元或2元的纸币，否则零钱总数将超过6元7⾓，第⼆次应选择1元的纸币（或硬币），然后是⼀枚5⾓的硬币，最后加⼊两个1⾓的硬币。

这种找零钱的⽅法就是贪⼼法。

选择要找的⼈民币时所采⽤的准则就是采取的贪⼼标准（或贪婪策略）。

贪⼼法（⼜称贪婪算法）是指在求最优解问题的过程中，依据某种贪⼼标准，从问题的初始状态出发，通过若⼲次的贪⼼选择⽽得出最优解或较优解的⼀种阶梯⽅法。

从贪⼼法“贪⼼”⼀词便可以看出，在对问题求解时，贪⼼法总是做出在当前看来是最好的选择。

也就是说，贪⼼法不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。

贪⼼法主要有以下两个特点：（1）贪⼼选择性质：算法中每⼀步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未作出的选择。

贪心算法

贪心算法

max vi xi
i 1
n
于是，背包问题归结为寻找一个满足约束条 件式，并使目标函数式达到最大的解向量X=(x1, x2, …, xn)。
至少有三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快 地增加背包的总价值。但是，虽然每一步选择获得 了背包价值的极大增长，但背包容量却可能消耗得 太快，使得装入背包的物品个数减少，从而不能保 证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可 能多的物品，从而增加背包的总价值。但是，虽然 每一步选择使背包的容量消耗得慢了，但背包的价 值却没能保证迅速增长，从而不能保证目标函数达 到最大。 （3）选择单位重量价值最大的物品，在背包价值 增长和背包容量消耗两者之间寻找平衡。
算法
main( ) { int i,j,n,GZ,A； int B[8]={0,100,50,20,10,5,2,1},S[8]; input(n); for(i=1;i<=n;i++) { input(GZ); for(j=1,j<=7;j++) { A=GZ/B[j]; S[j]=S[j]+A; GZ=GZ-A*B[j];} } for(i=1;i<=7;i++) print(B[i], “----”, S[i]); }
∞ b 4 0 a 8 h ∞ 4 b 4 0 a 8 h 8 11 7 11 7
8 ∞ i 6 1 2
∞ c
7
∞ d 14 9 e ∞ 10
4 g ∞
2
f ∞
(a)
8 ∞ i 6 1 g ∞ 2 4 f ∞ ∞ c 7 ∞ d 14 9 e ∞ 10 2
贪心法求解活动安排问题的关键是如何选择贪心策略，使 得按照一定的顺序选择相容活动，并能安排尽量多的活动。至 少有两种看似合理的贪心策略： （1）最早开始时间：这样可以增大资源的利用率。 （2）最早结束时间：这样可以使下一个活动尽早开始。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

贪心法的思想以及证明方法
摘要本文首先论述了贪心法的主要思想方法，针对利用贪心法的重要性质证明贪心法提出了自己的理解。

贪心法的应用简单，证明却很麻烦。

因此作者大胆猜想：是否可以将有相同性质的问题归类，按类进行证明，并给出了一类应用问题的证明过程。

关键词贪心法最优子结构性质贪心选择性质
我曾经向往着哲学的深邃和心理学的通透，而最终选择的是计算机专业。

我认为计算机发展不过百年却能有如此成就，它不受积年陈旧规则的制约，依然葆有活力；同时仍有大片的区域有待挖掘，富有创新的可能性。

它所运用的思想方法总是深刻而质朴，经几番思考研究，不仅有了新的理解，在对于事物的认识上也深有益处。

这个学期我们接触了计算机原理的知识。

这是由宏观到微观的学习，揭示了如今呈现在我们面前的成熟的计算机，是如何仅仅凭借一高一低的信号便实现了令人类惊叹的智慧与计算能力。

尤其对于磁盘的运用，虽不在课程范围内，但我却对它产生了很大兴趣。

磁盘能够实现存储功能的核心在于磁道与磁头，磁头平移到目的磁道从而实现对该磁道文件的读取。

磁头移动过程耗费的时间成为牵制访问速度的主要因素。

假设n个文件每个文件占据一条磁道，不同文件被访问概率也不同。

如将被访问概率最大的文件置于正中间的磁道，概率次大和第三大的文件分别置于其两边，按此方法依次放置所有文件就能够得到最佳的存储方式[1]。

其中核心的思想正是贪心法。

在数据结构与算法中，贪心法也是算法的基本方法之一，它被完美应用在求最小生成树的Prim算法和Kruskal算法中。

树是数据结构中的一种存储结构，由点集和边集构成。

最小生成树是树的全部点和部分能使树的总权值最小且同时保持连通的边构成的子树。

Prim 算法和Kruskal算法在本质上都是在每次递归中选择当前权值最小的边并纳入最小生成树。

贪婪法在计算机领域应用广泛，我想是因为贪婪法有着简单直接的构造方法和深刻的思想背景。

贪婪法是在解决问题的过程中，每一步都按照最优贪心标准作出当前情况下的最优选择，使得在做出选择后问题得以稍加简化。

经过多次贪心选择，最终达到总体最优解。

然而贪心法并不总是可行的，因为总是在没有排除过其他可选条件的情况下直接选择了局部最优解。

在用贪心法解得可能最优解后，则需要证明在此种情况下使用贪心法的合理性。

在一些教材以及前人的论述中，认为关键是证明当前问题存在贪心选择性质（全局最优解可以通过局部最优贪心选择达到）和最优子结构性质（问题的最优解包含了其子问题的最优解）[2]。

在对一些案例进行总结的基础上，我认为可以将证明思路进一步改进。

把最小子问题的最优解与产生此子问题的选择合并，并按此一步步向前进行合并，当还原至原问题时，若所得到的解是总体最优的，那么此问题可以用贪心法解决。

例如，经典的0-1背包问题是不适用贪心法的案例。

假如度量标准选取单位重量物品的价值，最小子问题是选择背包中的最后一个物品。

由于物品不可切分，多数情况下背包余量将不足以容纳任何所剩物品。

矛盾由此产生，若这个位置就此空置，会极大拉低背包利用率，所以此法不能得到最优解。

常见的对贪心法的应用中，大多是涉及到某一特定问题时针对其加以证明。

我认为可以将具有某些相同性质的问题归类，对这一类加以证明，从而使贪心法的应用更加便捷。

例如，对基于集合的问题作如下猜想：已知一个特定有限非空的集合A，求在某最优化条件下从A中选择出的元素所组成的非空新集合。

首先证明该问题的最优子结构性质。

设该问题最优解为集合B。

由于B非空，必有元素a属于B。

对于a产生的子问题，B中包含的它的解C也必是最优的。

这是因为，若存在C’比C更符合优化条件，那么C就不是子问题最优解。

用C’替代在B中属于C的元素，从而产生B’。

B’中元素应会比B更优化，即B’才是最优解。

这与原假设B是问题最优解产生矛盾，故原命题得证。

也就是证明了问题的最优解包含了其子问题的最优解。

根据最优子结构性质可以证明此问题也存在贪心选择性质。

由于总体最优解包含子问题最优解，用集合的“并”运算就可以从子问题和贪心选择构成全局最优解。

经过以上证明，我认为猜想是正确的。

它的实质是集合具有明确性、无序性、互异性，并由此衍生出的集合性质与运算。

同时也应当注意猜想使用的范围。

就如在0-1背包问题中，最后一个位置有可能不足以容纳任何物品，它的地位与其它位置是不平等的，这不同于集合中元素之间的关系，所以0-1背包不能套用该猜想。

尽管贪心法在千变万化的实际情况中的证明仍是使用者的难题，
它已然在各个学科中有了丰富的应用。

剥除复杂的学术环境，在生活中贪心法也已经烙印在人们的行为模式中。

当我们购物找钱的时候，每次总是选择不大于剩余应找数额的最大面值的货币，这样就能使找钱次数最少、速度最快。

这是贪心法细微而潜在的应用。

贪婪法无处不在，是因为它的思想本质是方法最直接、思路最浅显地达成目的，不设迂回，这也是人朴素的本能。

然而为它命名的人却很幽默。

贪婪属于西方宗教中的七宗罪，是逃离控制的欲望。

当欲望失去了枷锁，就没有了前进的路。

我想前人学者们也是想通过这一名字警醒世人：无论是贪婪法，还是内心的欲望，都应该有选择的谨慎对待。

参考文献
[1].肖美华，刘文革,优化文件分配及磁盘文件存储之策略.南昌航空工业学院学报, 2001. 3
[2].Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,Introduction to Algorithms,潘金贵（译）,顾铁成（译）,李成法（译），算法导论（第二版）.机械工业出版社。