数据结构课程设计报告(背包问题求解)-余玲

《数据结构》课程设计题目背包问题求解学生姓名余玲指导教师张晨光学院信息科学技术学院专业班级2011级数学与应用数学2班完成时间2013年12月27日1目录第一章课程设计目的........................................................................................2第二章课程设计内容和要求..............................................................................22.1课程设计内容..........................................................................................22.2课程设计要求.........................................................................................22.3运行环境.................................................................................................3第三章课程设计分析..........................................................................................33.1递归算法简介..........................................................................................33.2算法基本思想.........................................................................................33.3背包问题求解.........................................................................................4第四章算法（数据结构）描述..........................................................................44.1背包问题结构体.....................................................................................44.2质量及价值要求.....................................................................................44.3算法流程图.............................................................................................5第五章源代码......................................................................................................5第六章运行结果分析..........................................................................................7第七章结束语......................................................................................................8第八章参考文献..................................................................................................92第一章课程设计目的在大二下学期学习了《C++程序设计》课程的基础上，本学期我们学习了《数据结构（用面向对象方法与C++语言描述）》这门课程。《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科，是一门实践性非常强的课程，不仅需要在课堂上认真学习理论知识，更需要在课下自己在电脑上进行编程实验，以做到学以致用。为更好地理解与运用所学知识，提高动手能力，学校安排并进行了此次课程设计实习。该课程不但要求实习者掌握《数据结构（用面向对象方法与C++语言描述）》中的各方面知识，还要求实习者具备一定的语言基础和编程能力。能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术；具体说来，这次课程设计主要有两大方面目的。一是通过实习让实习者掌握《数据结构（用面向对象方法与C++语言描述）》中的知识。对于《背包问题求解》这一课题来说，所要求掌握的数据结构知识主要有：递归算法。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题；二是通过实习巩固并提高实习者的VisualC++语言知识，提高其编程能力与计算机专业水平。第二章课程设计内容和要求2.1课程设计内容设有不同价值，不同重量的物品n件，求从这n件物品中选取一部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。为使得问题更加清晰明了，我们将其转换为：给定n种不同的物品和一个背包，物品i的质量是Wi,背包容量是M，假定物品i的一部分xi(0xi1),被放进背包里,就会得到利润Pixi。因为背包的容量是M，要求被装进的物品的总质量不超过M（若只考虑物重而不考虑其形状和体积）问应怎样选择物品的种类和数量，使背包装满，而获得最大利润。此类问题的形式化描述是：给定M0，Wi0，Pi0，1in，要求找出一个n元向量(x1，x2，……xn)，0xi1，1in，使之满足约束条件niiiMxW1，使目标函数niiixP1达到最大.满足0x1的任何向量都是一个可能解.而最佳解必需是使目标函数的值达到最大的一个可能解.当约束xi为正整数时称为整数背包,当约定xi=0或xi=1时称为0-1背包.2.2课程设计要求（1）分别输入n件物品的重量和价值3（2）采用递归寻找物品的选择方案.（3）输出最佳的装填方案：包括选中的是哪几种物品，总价值为多少。.2.3运行环境该程序的运行环境为Windows7系统，MicrosoftVisualStudio2012版本。第三章课程设计分析3.1递归算法简介本课题要求采取递归的算法。递归是设计和描述算法的一种有力的工具，能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，然后从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。3.2算法基本思想递归算法根本思想是假设用布尔函数knap(s,n)表示n件物品放入可容质量为s的背包中是否有解(当knap函数的值为真时说明问题有解,其值为假时无解).我们可以通过输入s和n的值,根据它们的值可分为以下几种情况讨论:(1)当s=0时可知问题有解,即函数knap(s,n)的值为true;(2)当s0时这时不可能,所以函数值为false;(3)当输入的s0且n1时即总物品的件数不足1,这时函数值为false,只有s0且n≥1时才符合实际情况,这时又分为两种情况:(1)选择的一组物体中不包括Wn则knap(s,n)的解就是knap(s,n-1)的解.(2)选择的一组物体中包括Wn则knap(s,n)的解就是knap(s-Wn,n-1)的解.这样一组Wn的值就是问题的最佳解.这样就将规模为n的问题转化为规模为n-1的问题.综上所述0-1背包问题的递归函数定义为:10)1,()1,(1000),(nsnWnsknapnsknapnsfalsesfalsestruensknap且或且采用此法求解0-1背包问题的时间复杂度为O(n)。上述算法对于所有物品中的某几件恰能装满背包时能准确求出最佳解。但一般情况是对于某一些物品无论怎么装都不能装满背包，必须要按背包的最大容量来装。对于这种装不满的背包它的解决办法是这样的：按所有物品的组合质量最大的方法装背包，如果还装不满，则我们可以考虑剩余空间能否装下所有物品中最小的那件，如果连最小的都装不下了则说明这样得到的解是最佳解，问题解决。这样我们必须先找出所有n件物品中质量最小的那件（它的质量为Min），但是为了问题的解决我们不能增加运算次数太多，并且必须运用上述递归函数。那么我们可通过修改s的值即背包的容量，从背包容量s中减去k（它的值是从0到Min-1之间的一个整数值），再调用递归函数。当k=0时即能装满背包，其它值也能保证背包能最大限度装满，这样所有问题都解决了。43.3背包问题求解设n件物品的重量分别为w0、w1、…、wn-1，物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option[]，该方案的总价值存于变量maxV。当前正在考察新方案，其物品选择情况保存于数组cop[]。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxV时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxV大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。对于第i件物品的选择考虑有两种可能：(1)考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。(2)考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。采用option[]和cop[]两个数组来辅助完成递归寻找物品的选择方案。数组option[]起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop[]则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option[]，起到一个桥梁作用。第四章算法（数据结构）描述4.1背包问题结构体struct{//物品结构intweight;intvalue;}a[N];4.2质量及价值要求find(物品i当前选择已达到的重量和tw以及本方案可能达到的总价值tv){//考虑物品i包含在当前方案中的可能性if(包含物品i是可以接受的){将物品i包含在当前方案中;if(in-1)find(i+1,tw+物品i的重量,tv);else//又一个完整方案，因为它比前面的方案好，以它作为最佳方案以当前方案作为临时最佳方案保存;恢复物品i不包含状态;}5//考虑物品i不包含在当前方案中的可能性if(不包含物品i仅是可考虑的)if(in-1)find(i+1,tw,tv-物品i的价值);else//又一个完整方案，因它比前面