算法设计与分析第二版课后答案王红梅

【篇一：算法设计与分析论文】

心中爆发，就在贪心中灭亡

武汉理工大学计算机科学与技术学院班 摘要

本文介绍贪心算法的基本意义以及算法的使用范围，并通过具体的案例来分析贪心算法的具体应用，从而指出其特点和存在问题。 关键字：贪心算法，贪心策略，tsp、0/1背包 引言

我们用了13周的时间学完了《算法设计与分析》这本书。这本书中涵盖了大量的常见算法，包括蛮力法、分治法、动态规划法、贪心算法等等。我最有印象的就是贪心算法。贪心算法是一种有合理的数据组织和清晰高效的算法，它简单有效。下面我们来详细解读一下这个算法。

1. 贪心算法的含义

贪心算法可以简单描述为:对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 2. 贪心算法的基本思想

贪心算法，法如其名，每次都贪心的选取当前最优解，一旦确定了当前解，不管将来有什么结果，之后都不会再修正，这一点与动态规划法比起来稍有逊色。如果一个问题的最优解只能用蛮力法穷举得到，则贪心法不失为寻找问题近似最优解的一个较好办法。

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的

选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。 3. 贪心算法的基本要素 3.1 贪心选择

贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。 3.2 最优子结构

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退;动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。 4. 贪心算法的核心

贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。贪心策略决定着贪心算法是爆发或者是灭亡。所以，选择一个合理、正

确的贪心策略是至关重要的。下面用例子说明：

第一个例子我们选用大家熟知的0/1背包问题。给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。在选择物品i装入背包时，不可以选择物品i的一部分，一定要全部装入背包，1?i?n。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

设xi表示物品i装入背包的情况，根据问题的要求，有如下约束条件和目标函数： ?n

??wivi?c ?i?1

?0?x?1 (1?i?n) i?

max?vixi

i?1 n

于是，背包问题归结为寻找一个满足约束条件式，并使目标函数式达到最大的解向量x?(x1,x2,…,xn)。

现在有一个容量为50的背包，共有三个物品，重量为别为20、30、10，价值分别为60、120、50。现使用贪心算法来放置物品，贪心策略也对应有三种，分别是根据重量、价格、重量与价格比。

根据重量的贪心策略，即优先放置重量小的物品，以此来达到放置更多个物品的目的。首先需要将物品按照重量从小到大重新排序，然后从小到大的放置物品，直至下个物品无法放进背包为止。伪代码如下：

publicclass worsegreedy {

publicstaticvoid depweight(double[][] a, double c, int[] ans) // // on // the

// weight to select // goods {

double[] w = newdouble[a[0].length]; system.arraycopy(a[0], 0, w, 0, w.length); enumerationsearch sea = new enumerationsearch(); quick.sort(w); for (int i = 0; w[i] = c i w.length; i++) { c = c - w[i]; depend } }

ans[j] = 1;

程序的运行结果见附录。

根据价格的贪心策略，即优先放置价格比较高的物品，以此来达到背包价格更高的目的。首先需要将物品按照价格从大到小重新排序，然后依次放置物品，直至下个物品超出背包容量为止。伪代码如下： publicstaticvoid depprice(double[][] a, double c, int[] ans) // depend on

// the price // to select goods { }

double[] p = newdouble[a[1].length]; system.arraycopy(a[1], 0, p, 0, p.length); enumerationsearch sea = new enumerationsearch(); quick.sort(p); int i = (p.length - 1);

int j = sea.search(a[1], p[i]); while (a[0][j] = c i = 0) { } c = c - a[0][j]; ans[j] = 1; i--; j = sea.search(a[1], p[i]); 程序的运行结果见附录。

根据重量与价格比值的贪心策略，即优先放置“性价比”高的物品，以此来达到背包价格最大的目的。首先需要求出各个物品的价格与重量的比值，然后按照这个参数来重新排序物品，价重比高的放前面。最后一次放入物品，直至下个物品超出背包容量为止。伪代码如下：

publicstaticvoid depwepr(double[][] a, double c, int[] ans) { // depend on

// the // weight // and price

double[] w = newdouble[a[0].length]; // the weight of goods system.arraycopy(a[0], 0, w, 0, w.length); // copy the array system.arraycopy(a[1], 0, p, 0, p.length); // copy the array double[] pw = newdouble[w.length]; for (int i = 0; i w.length; i++)

// price/weight pw[i] = p[i] / w[i]; // weight and pw

double[][] wpw = newdouble[2][w.length]; // record the table of system.arraycopy(w, 0, wpw[0], 0, w.length); system.arraycopy(pw, 0, wpw[1], 0, w.length);

enumerationsearch sea = new enumerationsearch(); quick.sort(pw);

int i = (pw.length - 1);

int j = sea.search(wpw[1], pw[i]); while (wpw[0][j] = c i = 0) { } } c = c - wpw[0][j]; ans[j] = 1; i--; j = sea.search(wpw[1], pw[i]); 程序运行结果见附录。

根据程序运行的结果，我们分别得到三个答案。放置的物品方案分别为：

10?20、30?20、10?30。如此看来，根据价格的贪心策略是最“贪心”的。

其实不然，根据价格与重量比值的贪心策略的适应范围更加广阔，效果一般来说也更加的好。本例中受到小数据的局限性，无法发挥出其真正的效果。

贪心策略之所以能成为贪心算法的核心，就是因为它决定着贪心算法是爆发还是灭亡，以及爆发的程度。上面的例子用三种不同的贪心策略，结果也截然不同。当扩大问题规模时，这种差距就更加的明显。

5. 贪心算法的特点