背包问题大数据结构实验报告材料的.doc

淮阴工学院数据结构课程设计报告选题名称:背包问题求解系(院):计算机工程系专业: 计算机科学与技术班级:网络107姓名:蒋为维学号:1071304110指导教师:张亚红张勇军学年学期: 2008~2009学年第2学期 2009 年 6 月20 日设计任务书课题名称背包问题求解设计目的通过一周的课程设计,实现回溯法解决背包问题的方法,达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统VisualC++;编写代码,实现回溯法背包问题;撰写课程设计报告;参加答辩;,~,:2009年6月10日注意:任务书格式参照“任务书范例”执行。范例中的红色文字应根据你所选择的具体课题,修改为对应的内容。范例中的其它内容不变。摘要:组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点,这不仅在于其内在的复杂性有着重要的理论价值,同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是,往往由于问题的计算量远远超出了计算机在有效时间内的计算能力,使问题的求解变为异常的困难。尤其对于NP完全问题,如何求解其最优解或是近似最优解便成为科学的焦点之一。背包问题是一个典型的组合优化问题,在计算理论中属于NP-完全问题,其计算复杂度为,传统上采用动态规划来求解。设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整数规划模型:目标函数:(*)式中为0-1决策变量,时表示将物品装入背包中,时则表示不将其装入背包中。(实践周);,我负责设计数据结构,编写代码;;。(实践周)思想利用回溯法的设计思想来解决背包问题。首先将物品排列成一列,然后顺序选取物品装入背包,假设已选取了前i件物品后背包还没装满,则继续选取第i+1件物品,若该件物品“太大”不能装入