4-贪心算法

中 南 大 学

《算法设计与分析》实验报告

姓 名：

专 业 班 级：

学 号：

指导教师：

完成日期： 20010.1

一．实验名称

贪心算法实验

二． 实验目的

1. 了解贪心算法思想

2. 掌握贪心法典型问题，如背包问题、作业调度问题等。

三．实验内容

1. 编写一个简单的程序，实现单源最短路径问题

2. 编写一段程序，实现找零

3. 编写程序实现多机调度问题

四．算法思想分析

1.单源最短路径问题

（1）问题描述

已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

（2）算法分析

Dijkstra算法：

算法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。

2.找零问题

（1）问题描述

当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少） （2）问题分析计算法实现

根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。

假如要找77分钱，有上面的面值分别为25，10，5，1的硬币数，为了找最少的硬币数，那么他是不是该这样找呢，先看该找多少个25分的， 57／25＝2，好像是2个，要是3个的话，我们还得再给老板一个1分的，这样不行，那么只能给2个25分的，由于还少给27，所以还得给我2个10分的，1个5分的和2个1分。

1、 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

2、 背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包

3、 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

4、 给定字符及其相应出现次数，编写程序实现对这些字符的哈夫曼编码，最终打印出这些字符的编码。

5、 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。编写程序实现计算从源点到其它各个顶点的最短路径长度。并写出其路径。

6、 设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。给定带权图中定点和边的信息，编写程序画出最小生成树。

贪心算法求解最优解问题

贪心算法是计算机科学领域中常用的一种算法。它常常被用来求解最优解问题，如背包问题、最小生成树问题、最短路径问题等。贪心算法解决最优解问题的基本思路是，每一步都选取当前状态下最优的解决方案，直到达到全局最优解。在这篇文章中，我们将为大家深入探讨贪心算法求解最优解问题的基本思路、算法复杂度和应用场景等方面的知识。

基本思路

贪心算法是一种基于贪心策略的算法。其核心思想是，每一步都采用当前最优策略，以期最终达到全局最优解。在贪心算法中，每个子问题的最优解一般都是由上一个子问题的最优解推导出来的。因此，关键在于如何找到最优解。

具体而言，贪心算法一般由三部分组成，分别为：状态、选择和判断。首先，需要明确当前问题的状态，即问题的规模和限制条件。然后，在当前的限制条件下，我们需要从可能的方案中选择出最优的方案，并把这个选择作为解的一部分。最后，需要判断选择是否符合问题的限制条件，是否达到全局最优解。

算法复杂度

在进行算法分析时，我们需要考虑算法的时间复杂度和空间复杂度。对于贪心算法而言，其时间复杂度一般是 O(nlogn) 或 O(n)

级别的，其中 n 表示问题的规模。这种效率在实际应用中表现出了很高的稳定性和效率。

应用场景

贪心算法通常应用于需要求解最优解问题的场景中。例如：

- 贪心算法可以用来求解背包问题。在背包问题中，我们需要在限定的空间内选取最有价值的物品装入背包中以努力获得最大的收益。在贪心策略下，我们只需要按单位重量价值从大到小的顺序进行选择，就可以得到最优解；

- 贪心算法也可以用来求解最小生成树问题。这个问题是指，在给定一个图的时候，我们需要选出一棵生成树，使得生成树上的所有边权之和最小。在此问题中，我们可以将图上的边权按大小排序，然后顺序选择边直至生成树。这样，我们可以得到与全局最优解很接近的解；

- 贪心算法还可以用来求解最短路径问题。在最短路径问题中，我们需要找到从一个节点到另一个节点的最短路径。在贪心策略下，我们只需要选择当前节点能到达的距离最短的节点，不断迭代即可。这样，我们就可以得到最短路径。

列举贪心算法求解的经典问题

贪心算法是一种基于贪婪策略的算法，它在每一步选择中都采取当前状态下的最优决策，以期望能够得到全局最优解。以下是一些常见的经典问题，可以通过贪心算法来求解：

1. 零钱兑换问题（Coin Change Problem）：给定一些不同面额的硬币和一个要兑换的金额，找出使用最少的硬币数量来凑成该金额的方法。

2. 区间调度问题（Interval Scheduling Problem）：给定一组区间，每个区间都有开始时间和结束时间，目标是找到最大的不重叠区间子集。

3. 活动选择问题（Activity Selection Problem）：给定一组活动，每个活动都有开始时间和结束时间，目标是安排尽可能多的活动，使得它们不重叠。

4. 霍夫曼编码（Huffman Coding）：给定一组字符及其出现频率，通过构建霍夫曼树来生成最优的编码方案，使得出现频率高的字符具有较短的编码。

5. 最小生成树（Minimum Spanning Tree）：给定一个连通图，找到一个子图，使得它包含了所有的顶点且边的权重之和最小。

6. 最短路径问题（Shortest Path Problem）：给定一个图和起点，找到从起点到其他顶点的最短路径，其中边的权重可以是正数、负数或零。

这些问题都可以通过贪心算法求解，但需要注意的是，贪心算法并不总是能得到全局最优解，因此在使用贪心算法时要仔细分析问题的性质，确保贪心策略的正确性。