《数据结构》课程设计
题 目 背包问题求解 学生姓名 余 玲 指导教师 张晨光 学 院 信息科学技术学院 专业班级 2011级 数学与应用数学 2班 完成时间 2013年12月27日
目 录
第一章 课程设计目的 ........................................................................................ 2
第二章 课程设计内容和要求 .............................................................................. 2
2.1课程设计内容 .......................................................................................... 2 2.2 课程设计要求 ......................................................................................... 2 2.3 运行环境 ................................................................................................. 3 第三章 课程设计分析 .......................................................................................... 3
3.1递归算法简介 .......................................................................................... 3 3.2 算法基本思想 ......................................................................................... 3 3.3 背包问题求解 ......................................................................................... 4 第四章 算法（数据结构）描述 .......................................................................... 4
4.1 背包问题结构体 ..................................................................................... 4 4.2 质量及价值要求 ..................................................................................... 4 4.3 算法流程图 ............................................................................................. 5 第五章 源代码 ...................................................................................................... 5 第六章 运行结果分析 .......................................................................................... 7 第七章 结束语 ...................................................................................................... 8 第八章 参考文献 .................................................................................................. 9
1
第一章 课程设计目的
在大二下学期学习了《C++程序设计》课程的基础上，本学期我们学习了《数据结构（用面向对象方法与C++语言描述）》这门课程。《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科，是一门实践性非常强的课程，不仅需要在课堂上认真学习理论知识，更需要在课下自己在电脑上进行编程实验，以做到学以致用。为更好地理解与运用所学知识，提高动手能力，学校安排并进行了此次课程设计实习。该课程不但要求实习者掌握《数据结构（用面向对象方法与C++语言描述）》中的各方面知识，还要求实习者具备一定的语言基础和编程能力。能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术；
具体说来，这次课程设计主要有两大方面目的。
一是通过实习让实习者掌握《数据结构（用面向对象方法与C++语言描述）》中的知识。对于《背包问题求解》这一课题来说，所要求掌握的数据结构知识主要有：递归算法。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题；
二是通过实习巩固并提高实习者的Visual C++语言知识，提高其编程能力与计算机专业水平。
第二章 课程设计内容和要求
2.1课程设计内容
设有不同价值，不同重量的物品n件，求从这n件物品中选取一部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。
为使得问题更加清晰明了，我们将其转换为：
给定n种不同的物品和一个背包，物品i的质量是Wi,背包容量是M，假定物品i的一部分xi(0xi1),被放进背包里,就会得到利润Pixi。因为背包的容量是M，要求被装进的物品的总质量不超过M（若只考虑物重而不考虑其形状和体积）问应怎样选择物品的种类和数量，使背包装满，而获得最大利润。此类问题的形式化描述是：给定M>0，Wi>0，Pi>0，1in，要求找出一个n元向量(x1， x2，„„xn)，0xi1，1in，使之满足约束条件WixiM，使目标函数Pixii1i1nn达到最大.满足0x1的任何向量都是一个可能解.而最佳解必需是使目标函数的值达到最大的一个可能解.当约束xi为正整数时称为整数背包,当约定xi=0或xi=1时称为0 -1背包.
2.2 课程设计要求
（1）分别输入n件物品的重量和价值
2
（2）采用递归寻找物品的选择方案.
（3）输出最佳的装填方案：包括选中的是哪几种物品，总价值为多少。.
2.3 运行环境
该程序的运行环境为Windows 7系统，Microsoft Visual Studio 2012版本。
第三章 课程设计分析
3.1递归算法简介
本课题要求采取递归的算法。递归是设计和描述算法的一种有力的工具，能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，然后从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
3.2 算法基本思想
递归算法根本思想是假设用布尔函数knap(s,n)表示n件物品放入可容质量为s的背包中是否有解(当knap函数的值为真时说明问题有解,其值为假时无解).我们可以通过输入s和n的值,根据它们的值可分为以下几种情况讨论:(1)当s=0时可知问题有解,即函数knap(s,n)的值为true;(2)当s<0时这时不可能,所以函数值为false;(3)当输入的s>0且n<1时即总物品的件数不足1,这时函数值为false,只有s>0且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背包问题的递归函数定义为:
s0truefalses0knap(s,n)
s0且n1falses0且n1knap(s,n1)或knap(sWn,n1)采用此法求解0 -1背包问题的时间复杂度为O(n)。上述算法对于所有物品中的某几件恰能装满背包时能准确求出最佳解。但一般情况是对于某一些物品无论怎么装都不能装满背包，必须要按背包的最大容量来装。对于这种装不满的背包它的解决办法是这样的：按所有物品的组合质量最大的方法装背包，如果还装不满，则我们可以考虑剩余空间能否装下所有物品中最小的那件，如果连最小的都装不下了则说明这样得到的解是最佳解，问题解决。这样我们必须先找出所有n件物品中质量最小的那件（它的质量为Min），但是为了问题的解决我们不能增加运算次数太多，并且必须运用上述递归函数。那么我们可通过修改s的值即背包的容量，从背包容量s中减去k（它的值是从0到Min -1之间的一个整数值），再调用递归函数。当k=0时即能装满背包，其它值也能保证背包能最大限度装满，这样所有问题都解决了。
3
3.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 { //物品结构 int weight; int value; }a[N];
4.2 质量及价值要求
find(物品i当前选择已达到的重量和tw以及本方案可能达到的总价值tv) {//考虑物品i包含在当前方案中的可能性 if(包含物品i是可以接受的) {将物品i包含在当前方案中; if(i //又一个完整方案，因为它比前面的方案好，以它作为最佳方案 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } 4 //考虑物品i不包含在当前方案中的可能性 if(不包含物品i仅是可考虑的) if(i //又一个完整方案，因它比前面的方案好，以它作为最佳方案 以当前方案作为临时最佳方案保存;} 4.3 算法流程图 开始 键入对应质量和价值 键入最大的承受重量 Y 物品i是否被选择 N 不超过限制重量 可获得更大价值组 获得最优组合 输出选中物品及总价值 图4-1 算法流程图 第五章 源代码 #include int limitW, //背包指定的限制重量 totV, //全部物品的总价 maxV; //可实现的最大总价值 int option[N], //方案的选择 cop[N]; //当前的方案选择 struct { //物品结构 5 int weight; int value; }a[N]; int n; //物品种类数 void find(int i,int tw,int tv) { int k; if(tw+a[i].weight<=limitW) //考虑物品i包含在当前方案中的可能性 { cop[i]=1; if(i else{ for(k=0;k cop[i]=0; } if(tv-a[i].value>maxV) //考虑物品i不包含在当前方案中的可能性 void main() { int k,w,v; printf(\"请输入物品的种类数:\"); scanf(\"%d\ 6 if(i else{ for(k=0;k maxV=tv-a[i].value; } } for(totV=0,k=0;k printf(\"请输入背包的限制重量:\"); scanf(\"%d\ maxV=0; for(k=0;k find(0,0,totV); printf(\"最佳填装方案是:\\n\"); for(k=0;k printf(\"第%d种物品\\n\ printf(\"背包的总价值为:%d\\n\} 第六章 运行结果分析 此处我们举一个小数据事例对程序进行验证： 假设有5种不同质量不同价值的物品需要放进限制重量为10kg背包，其重量和价值如表6-1所示： 表6-1 事例数据 物品编号 重量（kg） 价值 1 2 10 2 3 6 3 4 8 4 1 9 5 6 5 在Windows 7系统，Microsoft Visual Studio 2012环境下运行上文的源代码，输入相应的数据，得到如图6-1所示的结果。 7 图6-1 背包问题求解界面 分析结果可以得到最佳方案为：选取第1种、第2种、第3种以及第4种物品放入背包，此时所放物品既没有超过背包的限制重量，而且所得的价值达到最大值33。按照生活常识，我们可以通过人工计算得到最佳方案与运行程序所得的结果一致。由此验证了，上述解决背包问题的程序是切实可行的。 第七章 结束语 这几天的《数据结构》课程设计过程可谓一言难尽。整天都是对着电脑查资料，编代码。在此期间我一度热情高涨，但也曾失落过，点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。 这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也时用错了方法，总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。 根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点： 8 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 第八章 参考文献 1． 殷人昆 陶永雷 谢若阳 盛绚华 ，数据结构（用面向对象方法与C++描述） 清华大学出版社 2． 赵专政. 0-1背包问题的递归算法[J]. 益阳师专学报,2002,06:50-52. 3． 孙红丽. 背包问题的算法设计与分析研究[J]. 电脑知识与技术,2008,25:1534-1535. 4． 迭代算法与 的概念及区别(下)（转载） http://hi.baidu.com/kingcham/item/00b865f0db6e320d84d278cb 5． 递归法求01背包问题 http://wenku.baidu.com/link?url=Q64hWF7tQRqEvlMu-ZOpsDnfLsKwhmxttwg_fkmTmV2qA55ZRi9db5NHcpdD58rs8PPu5YzzGsl4GsjXcBYrJ2P7Ohr31AVLO0R_nNKBxp_ 9 因篇幅问题不能全部显示，请点此查看更多更全内容