背包问题数据结构实验报告..doc

淮阴工学院数据结构课程设计报告选题名称:背包问题求解系(院):计算机工程系专业:计算机科学与技术班级:网络107姓名:蒋为维学号:1071304110指导教师:张亚红张勇军学年学期:2008~2009学年第2学期2009年6月20日设计任务书课题名称背包问题求解设计目的通过一周的课程设计,实现回溯法解决背包问题的方法,达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统VisualC++;,实现回溯法背包问题;;;,~,:2009年6月10日注意:“任务书范例”执行。..文字应根据你所选择的具体课题,修改为对应的内容。范例中的其它内容不变。摘要:组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点,这不仅在于其内在的复杂性有着重要的理论价值,同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是,往往由于问题的计算量远远超出了计算机在有效时间内的计算能力,使问题的求解变为异常的困难。尤其对于NP完全问题,如何求解其最优解或是近似最优解便成为科学的焦点之一。背包问题是一个典型的组合优化问题,在计算理论中属于NP-完全问题,其计算复杂度为)2(On,传统上采用动态规划来求解。设w[i]是经营活动i所需要的资源消耗,M是所能提供的资源总量,p[i]是人们经营活动i得到的利润或收益,则背包问题就是在资源有限的条件下,追求总的最大收益的资源有效分配问题。关键词:背包问题,堆栈,回溯法,递归目录1需求分析……………………………………….……………(实践周)题目……………………………………….………………(实践周)任务及要求…………………………….…………………(实践周)思想……………………………………….…………………………………………………….………………22概要设计………………………………………………..………………………………………….…………………………………………………………………..…………………………………………………………………………..……………………………………………………….…………………………………………………………….……63代码设计………………………………………………..…………………………………………………………….………………………………………………………………….……………………………………………………………………….……………………………………………………………………………….……………………………………………………………………………….………………………………………………………………………….…………84调试与操作说明……………………………………..………95总结………………………………………………….………116致谢…………………………………………………….……127参考文献…………………………………………….………(实践周)题目假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…,wn的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wn=T,要求找出所有满足上述条件的解。例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解:(1,4,3,2)(1,4,5)(8,2)(3,5,2)该问题的模型可以表示为下述0/1整数规划模型:目标函数:???niiinxcxxxf121),,(max???????????),2,1(}1,0{?(*)式中ix为0-1决策变量,1?ix时表示将物品i装入背包中,0?ix时则表示不将其装入背包中。(实践周);,我负责设计数据结构,编写代码;;。(实践周)思想