淮阴工学院
数据结构课程设计报告
选题名称:背包问题求解
系（院）:计算机工程系
专业:计算机科学与技术
班级:网络107
姓名:蒋为维学号: ********** 指导教师:张亚红张勇军
学年学期:2008 ~ 2009 学年第 2 学期2009 年 6 月20 日
设计任务书
注意：
1．任务书格式参照“任务书范例”执行。
2．范例中的红色
．．文字应根据你所选择的具体课题，修改为对应的内容。
范例中的其它内容不变。
摘要：
组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP 完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。背包问题是一个典型
的组合优化问题，在计算理论中属于NP-完全问题， 其计算复杂度为
)2(O n ，传统上采用动态规划来求解。设w[i]是经营活动 i 所需要的资源消耗，M 是所能提供的资源总量，p[i]是人们经营活动i 得到的利润或收益，则背包问题就是在资源有限的条件下， 追求总的最大收益的资源有效分配问题。
关键词：背包问题，堆栈，回溯法，递归
目录
1 需求分析 (1)
1.1课程设计（实践周）题目 (1)
1.2课程设计（实践周）任务及要求 (1)
1.3课程设计（实践周）思想 (1)
1.4软硬件运行环境及开发工具 (2)
2概要设计 (2)
2.1本课题设计所用数据结构以及流程图 (2)
2.1.1栈的原理 (2)
2.1.2溯法介绍 (3)
2.1.3包问题整体流程图 (5)
2.2本课题主要设计思想 (6)
3代码设计 (6)
3.1定义栈和顺序表结构体 (6)
3.2栈的初始化 (7)
3.3判断栈空 (7)
3.4入栈 (7)
3.5出栈 (8)
3.6输入元素 (8)
4调试与操作说明 (9)
5总结 (11)
6致谢 (12)
7参考文献 (13)
1需求分析
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整数规划模型：
目标函数：∑==n
i i i n x c x x x f 121),,(max
⎪⎩⎪⎨⎧=∈≤∑=)
,2,1(}1,0{t .s 1n i x p x w i n i i i i （*） 式中i x 为0-1决策变量，1=i x 时表示将物品i 装入背包中，0=i x 时则表示不将其装入背包中。
1.2课程设计（实践周）任务及要求
1.搜集背包问题方面的资料；
2.作为组长，我负责设计数据结构，编写代码；彭建鑫设计流程图和回
溯法介绍
3.撰写课程设计报告；
4.参加答辩。
1.3课程设计（实践周）思想
利用回溯法的设计思想来解决背包问题。首先将物品排列成一列，然后
顺序选取物品装入背包，假设已选取了前i件物品后背包还没装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而选取下一件，直到背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那见物品“不合适”，应该将它去出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯法求解的规则是“后进先出”因此自然要用到栈。
1.4软硬件运行环境及开发工具
Windows2000以上操作系统
Visual C++6.0以上编译环境
2概要设计
2.1 本课题设计所用数据结构以及流程图
2.1.1栈的原理
作为组长，我主要是负责该部分。背包问题求解涉及到的数据结构主要是栈，下面我就详细的介绍一下有关栈方面的知识。
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。当用一维数组存储栈时，被称为顺序栈。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）；
(2)当表中没有元素时称为空栈，用Top==-1表示；
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
栈为后进先出（Last In First Out）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。流程图如下：
Push(进栈)
Pop(出栈)
栈的基本运算：
（1）InitStack（S）
构造一个空栈S。
（2）StackEmpty（S）
判栈空。若S为空栈，则返回TRUE，否则返回FALSE。
（3）StackFull（S）
判栈满。若S为满栈，则返回TRUE，否则返回FALSE。
注意：该运算只适用于栈的顺序存储结构。
（4）Push（S，x）
进栈。若栈S不满，则将元素x插入S的栈顶。
（5）Pop（S）
退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
（6）StackTop（S）
取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。2.1.2回溯法介绍
此部分由彭建鑫设计。
1．什么是回溯法
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，
