算法设计与分析

《算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉工商学院信息工程学院学生姓名：王九四学号：14401019班级：14计科本数据处理实验班2015年10月10曰目录1鵬1.1问题概述11.2目的与任务11.2.1g的：11.2.2任务：11.3开发环境12贪心算法简介22.1贪心算法思想：22.2贪心算法的基木要素：22.3贪心算法解决竹包问题有几种策略：23使用贪心算法解决背仅闷题的实验及结果分析33.1解决思路33.2算法设计33.2.1核心算法流程图33.2.2核心代码及解释43.2.3吋间复杂度分析53.3算法结果63.3.1实验结果63

2、.3.2实验结果分析64递归算法简介74.1递归算法的特点74.2递归算法要求75使用递归算法解决n个元素全排列问题的实验及结果分析85.1解决思路85.2算法设计85.2.1核心算法流程图85.2.2核心代码及解释95.2.3吋间复杂度分析105.3算法结果105.3.1实验结果105.3.2实验结果分析116126.1贪心与递归算法总结126.2收获与不足126.3创新与特色121概述1.1问题概述0/1背包问题描述：0-1背包问题：给定n种物品和一个背乜。物品i的熏M是Wi，其价值为Vi，背包的

3、容fi为C。应如何选择裝入背包的物品，使得裝入背包中物品的总价值敁大？在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包⑴或不装入背包(0)。不能将物品i装入背包多次，也不能只装入部分的物品i。竹包问题：与()-1竹包问题类似，所不同的是在选择物品i装入竹包时，可以选择物品i的一部分，而不一定要全部装入背包，KiSn。背包问题可以定义如下：给出n个大小为sl，s2，...，sn，值为vl，v2，...，vn的项鬥，并设背色容量为C，嬰找到非负实数xl，x2,...,xn，使和在约束下最大。全

4、排列M题描述：没R={rl,r2.....rn}是要进行排列的n个元素，Ri=R-{rl}o集合X屮元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：当n=l,perm(R)=(r)，其中r是集合R中唯一的元素。当n〉l,perm(R)由(rl)perm(RI)，(r2)perm(R2),...(rn)perm(Rn)构成o1.2目的与任务1.2.1目的：本课程是信息与计算科学专业重耍的实践性环节之一，是在学

5、生学习完《算法设计与分析》课程P进行的一次全面的综合练习。本没计的目的和任务：(1)巩阀和加深学生对木课程的基本知识的理解和学握；(2)掌握基木算法的设计与实现；(3)掌握算法设计的基木思想；(4)提尚解决实际I'mJ题的能力；(5)掌握书写程序设计说明文档的能力。1.2.2任务：(―)设计什容：给出多种可以用贪心算法解决的典型M题，并分析、证明、编程。(二)设计要求：(1)贪心算法的基本思想；(2)给出背包问题的贪心算法和程序；(3)给出有限期计算机作业调度的贪心算法和程序；(4)给!11哈弗曼编码

6、问题的贪心算法和程序；(5)总结哪些问题可以使用贪心兑法；(6)总结贪心算法与动态规划算法区别。1.3开发环境VisualC++6.02贪心算法简介2.1贪心算法思想：顾名思义，贪心算法总足作出在当前看來最好的选择。也就是说贪心算法丼不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也足整体鉍优的。也然贪心兑法不能对所冇问题都得到整体鉍优解，但对许多问题它能产生整体最优解。如单源最短路经M题，最小生成树W题等。在一些情况下，即使贪心算法不能得到整体最优解，

7、其最终结果却是最优解的很好近似。2.2贪心算法的基木要素：(1)贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这足贪心算法可行的第一个基本要素，也足贪心算法与动态规划算法的主耍区別。动态规划算法通常以自底向上的方式解各了问题,而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规梭更小的子问题。对于一个具体问题，要确定它是否具冇贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

8、(2)当一个M题的最优解乜含其子

9、4题的最优解吋，称此问题具有最优子结构性质。M题的最优子结构性质足该问题可川动态规划算法或贪心算法求解的关键特征。2.3贪心算法解决背包闷题冇几种策略：(1)一种贪婪准则为：从剩余的物品屮，选出可以装入背包的价值最人的物品，利川这种规则，价值敁大的物品首先被装入(假设有足够容S),然后是下一个价值大的物品，如此继续卜*去。这种策略不能保证得到最优解。例如，考虑n=2，w=L100，10,10hp=l20，15，15hc=