资源描述：
《结课论文说明书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、塔里木大学结课论文1．前言1．1选题的背景和意义算法研究是计算机科学的核心。近年来，算法领域取得了很多重要的进展。这些进展包括快速算法的开发，如发明了傅里叶变换快速算法，以及不存在有效算法的本质问题的惊人发现。这些结果点燃了计算机学者对算法研究的兴趣。算法设计与分析也成为一个受到广泛注意的领域。1．2应用技术领域及范围算法设计和分析的应用领域极为广泛，比如，利用算法解决八皇后问题、背包问题等。1.3设计的原理和内容本次程序设计采用C语作为描述和实现算法的程序语言，主要用到的算法是贪心算法。贪心算法是从问题的初始状态出发，通过若干
2、次的贪心选择而得出当前最优值。利用贪心算法解决背包问题是指同时兼顾物品的价值和数量两个因素，既而选择单位数量价值最大的物品，最后得出的便是最优解。2．程序概况2.1程序所用的时间从这个程序开始到结束总共历时十四天。完成于2009年12月3日。2.2程序负责人周丹，女，计算机科学与技术11-2，学生。2.3程序指导人陈杰，男，信息工程学院教师，讲师。3．正文3.1设计的目的和意义我们是计算机科学与技术专业的本科生，《计算机算法的设计与分析》是我们重要的必修课程。当代社会学要大学培养出理论扎实，动手实践能力强的大学生。所以，本次课程
3、设计的目的就在于通过一次实践性的活动加深对这门课程的理解，使我们在感性的认识上进一步升华为理性的认识。为后继课程的学习打下坚实的基础。马克思主义唯物辩证法认为，实践是连接客观实在和人主观意识的通道和桥梁。物质对意识的作用以及意识对物质的反作用都蕴含在实践活动当中。也就是，实践是检验真理的唯一标准。对这门课的学习状况的好坏，用一次课程设计便可以检验出来。而这，就是本次我们进行设计的意义之所在。3.2目标和总体方案本次程序设计主要是用贪心算法解决背包问题。前段时间：查阅有关贪心算法解决背包问题的相关资料和设计本次课程设计的基本思路和
4、流程。后段时间：编写程序代码并进行调试和完善并整理本次课程设计和撰写《结课论文》。3.3设计方法和内容在这个程序的设计上，选择Ｃ语言作为算法的描述语言，因为Ｃ语言具有丰富的表达能力以及代码的高效性，并且有着良好的移植性和灵活性。同时，采用“自顶向下，个个击破”的程序设计思路和思想，充分运用Ｃ语言强大的功能，利用贪心算法解决背包问题。3.4设计流程图该程序的设计流程图如图3-1所示：第5页共5页塔里木大学结课论文开始输入物品总数输入各个物品的重量输入各个物品的价值输入背包的最大容量计算每个物品的单价(价值/重量)根据单价的大小进行
5、降序排序按照单价大的优先规律装包判断背包是否装满否输出结果是结束图3-1程序流程图3.5详细设计内容程序设计的基本算法介绍1、贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得出当前最优值的一种解题方法。“贪心”一词的意思是，贪心算法总是做出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。背包问题是指已知一个容量为M的背包和n种物品，每个物品i的重量为Wi，价值为Pi，可以分开装包（即选择其中的一部分
6、装包），求选择那些物品以及它们分别选择多少重量来装包，在总重量不超过包的容量M的前提下使包中所装物品的总价值达到最大？按照原问题的意思，即要求找出一组值（x1,x2,……,xn）,使得∑ni=1(wi*xi)<=M,且∑ni=1（pi*xi）最大。背包问题面临着价值和重量两个方面的因素，若第一种方案是价值优先，也就是说，每一步都是选择具有最大价值的物品，如果某物品被选择，因为包的限制不能装进去，则只能取适当的物品装包，使得包装满；第二种方案是物品数量优先，也就是说使得装入包的物品的数量尽可能多。按照这两种贪心策略得到的两个解都不
7、会是最优解，因为这两种策略都只考虑了其中的某一个因素，而没有同时兼顾价值和数量两个因素，所以最后得出的解肯定不是使∑ni=1(wi*xi)<=M且目标函数∑ni=1（pi*xi）最大的解。而利用贪心算法解决背包问题是指同时兼顾物品的价值和数量两个因素，既而选择单位数量价值最大的物品，先从单位重量第5页共5页塔里木大学结课论文价值最大的物品开始装包，然后再装单位重量价值次大的物品，依此类推，直至背包容量达到最大值为止，既而得出的各个物品所装的数量便是最优解。2、背包问题的基本操作:#definemax100/*宏定义变量*/mai
8、n(){intm,n,i,j,k,sum,jb[max];/*定义自变量*/floatw[max],p[max],M,pw[max],c[max],t,x[max];printf("qingshuruwupindezhongshu:");/*输入物品的总数*
