贪心算法的实验报告

《贪心算法的实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建工程学院计算机与信息科学系实验报告2012–2013学年第一学期任课老师：章静课程名称结构化程序设计班级座号姓名实验题目实验2贪心算法设计技术的应用实验时间实验开始日期：2012-12-11报告提交日期：2012-12-25实验目的、要求一、算法设计技术贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。例1：找零钱，一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25分、10美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心策

2、略如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩67美分，首先入选的是两枚25美分的硬币，第三枚入选的不能是25美分的硬币，否则硬币的选择将不可行（零钱总数超过67美分），第三枚应选择10美分的硬币，然后是5美分的，最后加入两个1美分的硬币。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。可以证明采用上述贪心算

3、法找零钱时所用的硬币数目的确最少。利用贪心策略解题，必须考虑两个问题，首先，问题是否适合于用贪心策略求解；其次，是在确定了可以用贪心策略之后，如何选择一个贪心标准，才能保证得到问题的最优解。例2：背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。采用怎样的装货方法，才能使装入背包的货物总价值达到最大?【分析】当货物总重量∑Wi小于或等于M时，把所有货物装入，总价值就达到最大。因此，关键是解决当总重量大于M时装货的方法。我们先从一个具体例子入手来研究一下本题的特点。设n=3；M=20。W1=15W2=10W3=8P1=18P2=15

4、P3=10有几种可能解（设Xi为第i种货物所取的重量）：X1X2X3总重∑Xi总价值∑PiXi/Wi(1)10552025.75(2)101002027(3)21082027.4(4)40162022.4显然第3个解总价值最大。5/6上述可能解是采用穷举方法试探所得众多可能解中的4种，这在具体的程序编制和实现过程中相当麻烦，且在时间复杂度上很难承受，是否可以寻找到一种简单而又时间效率高的方法呢？下面用贪心策略来解此题。首先应该确定贪心的量度标准。一种设想是按价值大小作为标准，先放价值最大的货物，再放价值次大的货物。即按价值从大到小顺序放置。则有方案：∵P1>P2>P3∴放置顺序为X1，X2，X

5、3取X1＝15，X2＝5，得到∑P＝X1P1+X1P2＝18＋7.5=25.5得到的不是最优解。表明用价值作为量度标准是错误的。原因是什么呢?原因是价值大的重量也大，我们按价值大的先放，造成重量消耗过快。由此启发我们用Pi/Wi（单位重量价值）来作量度标准，则有：U1=P1/W1=1.2U2=P2/W2=1.5U3=P3/W3=1.25因此放置顺序是X2，X3，X1，即有：X2=10X3=8X1=2∑XiUi=15+10+2.4=27.4这才是最优解。下面给出算法的简单描述：Begin读入数据；计算货物的单位重量价值Ti=Pi/Wi，并将它们从大到小排序；依次选择单位重量较大的货物装入背包，直

6、至不能装入；输出最大价值总和S和装货方案；End;二、实验题目1．利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。设计程序给出装货方法，使装入背包的货物总价值达到最大。2．设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20，10，5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。三、实验要求1．该实验的课内学时是4个课时。2．题目1必须完成。3．题目1在完成上述基本功能的前提下

7、，有能力的同学可以完成题目2。实验步骤与内容5/6按如下顺序写：1、主要设计思想:(1)第一题的关键是装入背包的货物的性价比要最高。按照性价比的顺序从高到低依次排列，同时还要注意背包的载重量。(2)第二题的关键是找零，将零钱一步一步取整就可以了。2、主要数据结构及其解释：第一题：（1）&&&&&&&&对单位重量值进行冒泡排序&&&&&&&&Sort(intn)（2）&&&&&将排好序的货物依次放入