淮阴工学院数据结构课程设计报告选题名称:背包问题求解系（院）:计算机工程系专业:计算机科学与技术班级:网络107姓名:蒋为维学号:1071304110指导教师:张亚红张勇军学年学期:2008~2009学年第2学期2009年6月20日设计任务书课题名称背包问题求解设计目的通过一周的课程设计，实现回溯法解决背包问题的方法，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统VisualC++6.0以上编译环境任务要求搜集背包问题方面的资料；编写代码，实现回溯法背包问题；撰写课程设计报告；参加答辩；工作进度计划序号起止日期工作内容12009.06.08理论辅导，搜集资料22009.06.08~2009.06.10编写代码，上机调试32009.06.11撰写课程设计报告42009.06.12答辩指导教师：2009年6月10日注意：任务书格式参照“任务书范例”执行。范例中的红色文字应根据你所选择的具体课题，修改为对应的内容。范例中的其它内容不变。摘要：组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其计算复杂度为，传统上采用动态规划来求解。设w[i]是经营活动i所需要的资源消耗，M是所能提供的资源总量，p[i]是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词：背包问题，堆栈，回溯法，递归目录1需求分析……………………………………….……………11.1课程设计（实践周）题目……………………………………….………………11.2课程设计（实践周）任务及要求…………………………….…………………11.3课程设计（实践周）思想……………………………………….………………11.4软硬件运行环境及开发工具…………………………………….………………22概要设计………………………………………………..……22.1本课题设计所用数据结构以及流程图…………………………………….……22.1.1栈的原理……………………………………………………………..………22.1.2溯法介绍…………………………………………………………………..…32.1.3包问题整体流程图…………………………………………………….……52.2本课题主要设计思想……………………………………………………….……63代码设计………………………………………………..……63.1定义栈和顺序表结构体……………………………………………………….…63.2栈的初始化……………………………………………………………….………73.3判断栈空……………………………………………………………….…………73.4入栈…………………………………………………………………….…………73.5出栈…………………………………………………………………….…………83.6输入元素……………………………………………………………….…………84调试与操作说明……………………………………..………95总结………………………………………………….………116致谢…………………………………………………….……127参考文献…………………………………………….………131需求分析1.1本课程设计（实践周）题目假设有一个能装入总体积为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决策变量，时表示将物品装入背包中，时则表示不将其装入背包中。1.2课程设计（实践周）任务及要求1.搜集背包问题方面的资料；2.作为组长，我负责设计数据结构，编写代码；彭建鑫设计流程图和回溯法介绍3.撰写课程设计报告；4.参加答辩。1.3课程设计（实践周