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

《数据结构》课程设计 题 目 背包问题求解 学生姓名 余 玲 指导教师 张晨光 学 院 信息科学技术学院 专业班级 2011级 数学与应用数学 2班 完成时间 2013年12月27日  目 录 第一章 课程设计目的 2 第二章 课程设计内容和要求 2 2.1课程设计内容 2 2.2 课程设计要求 3 2.3 运行环境 3 第三章 课程设计分析 3 3.1递归算法简介 3 3.2 算法基本思想 3 3.3 背包问题求解 4 第四章 算法（数据结构）描述 4 4.1 背包问题结构体 4 4.2 质量及价值要求 5 4.3 算法流程图 5 第五章 源代码 6 第六章 运行结果分析 8 第七章 结束语 8 第八章 参考文献 9 第一章 课程设计目的 在大二下学期学习了《C++程序设计》课程的基础上，本学期我们学习了《数据结构（用面向对象方法与C++语言描述）》这门课程。《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科，是一门实践性非常强的课程，不仅需要在课堂上认真学习理论知识，更需要在课下自己在电脑上进行编程实验，以做到学以致用。为更好地理解与运用所学知识，提高动手能力，学校安排并进行了此次课程设计实习。该课程不但要求实习者掌握《数据结构（用面向对象方法与C++语言描述）》中的各方面知识，还要求实习者具备一定的语言基础和编程能力。能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术； 具体说来，这次课程设计主要有两大方面目的。 一是通过实习让实习者掌握《数据结构（用面向对象方法与C++语言描述）》中的知识。对于《背包问题求解》这一课题来说，所要求掌握的数据结构知识主要有：递归算法。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题； 二是通过实习巩固并提高实习者的Visual C++语言知识，提高其编程能力与计算机专业水平。 第二章 课程设计内容和要求 2.1课程设计内容 设有不同价值，不同重量的物品n件，求从这n件物品中选取一部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。 为使得问题更加清晰明了，我们将其转换为： 给定n种不同的物品和一个背包，物品i的质量是Wi,背包容量是M，假定物品i的一部分xi(0xi1),被放进背包里,就会得到利润Pixi。因为背包的容量是M，要求被装进的物品的总质量不超过M（若只考虑物重而不考虑其形状和体积）问应怎样选择物品的种类和数量，使背包装满，而获得最大利润。此类问题的形式化描述是：给定M0，Wi0，Pi0，1in，要求找出一个n元向量(x1， x2，……xn)，0xi1，1in，使之满足约束条件，使目标函数达到最大.满足0x1的任何向量都是一个可能解.而最佳解必需是使目标函数的值达到最大的一个可能解.当约束xi为正整数时称为整数背包,当约定xi=0或xi=1时称为0 -1背包. 2.2 课程设计要求 （1）分别输入n件物品的重量和价值 （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时可知问