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

淮阴工学院
数据结构课程设计报告
选题名称: 背包问题求解
系（院）: 计算机工程系
专 业: 计算机科学与技术
班 级: 网络107
姓 名: 蒋为维 学 号: 1071304110
指导教师: 张亚红 张勇军
学年学期: 2008 ~ 2009 学年 第 2 学期
2009 年 6 月 20 日
14

设计任务书
课题
名称
背包问题求解
设计
目的
通过一周的课程设计，实现回溯法解决背包问题的方法，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。
实验
环境
Windows2000以上操作系统
Visual C++6.0以上编译环境
任务
要求
1. 搜集背包问题方面的资料；
2. 编写代码，实现回溯法背包问题；
3. 撰写课程设计报告；
4. 参加答辩；
工作进度计划
序号
起止日期
工 作 内 容
1
2009.06.08
理论辅导，搜集资料
2
2009.06.08~2009.06.10
编写代码，上机调试
3
2009.06.11
撰写课程设计报告
4
2009.06.12
答辩
指导教师：
2009 年 6 月 10 日
注意：
1． 任务书格式参照“任务书范例”执行。
2． 范例中的红色文字应根据你所选择的具体课题，修改为对应的内容。
范例中的其它内容不变。
摘要：
组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， 其计算复杂度为，传统上采用动态规划来求解。设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整数规划模型：
目标函数：
（*）
式中为0-1决策变量，时表示将物品装入背包中，时则表示不将其装入背包中。
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(进栈)
a0 a1 …… a n-1

Pop(出栈)
top(栈顶)
栈的基本运算：
（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． 什么是回溯法
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
2． 基本思想
回溯即是较简单、较常用的搜索策略。全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。
可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。
解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。
我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i>j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
2.1.3包问题整体流程图
输入预期总体积T

输入各物体体积

否

是
输入是否为0结束

计算总体积sum

否
sum是否等于T

是

输出解

图2-1 整体流程图
2.2 本课题设计的思想
本算法采用先进后出的算法来一个一个测试可行的全部解，所以很显然要用到栈。我通过建立顺序表来录入我要输入的各个物体的体积，然后通过结构体类型定义栈，把顺序表中的各个物体逐一入栈，如果各物体体积总和sum比我预定的目标体积小，那就继续入栈，有合适的组合则输出，否则说明刚才选入的物体体积即栈最顶端的那个不适合导致后面没有合适的解，所以把它POP掉，然后从它后面继续选取所要考察的物体体积。当第一个物体做栈底的所有情况满足后，我们就要考虑以第二个物体为栈底的情况，其实我并没有把第一个物体出栈，只是我读的时候把第一个物体“屏蔽”了，也就是说它虽然在栈中，但是我不考虑它，而是考虑新的栈也就是总栈中截取的我需要的那部分目标栈段，依次类推，当顺序表中所有物体都做过“栈底”后，那么就没有物体可以作为参数入栈或出栈了，所有循环结束。本算法采用3重while循环嵌套来实现算出所有不重复的解。
3代码设计
3.1 定义栈和顺序表结构体
typedef struct
{
int last;
int data[maxsize];
}seqlist; //定义一个顺序表结构体变量

typedef struct
{
int top;
int sum;
int data[maxsize];
}seqstack; //定义一个栈结构体变量

3.2 栈初始化
seqstack *init_seqstack()
{
seqstack *s;
s=new seqstack; //动态生成一个结构体变量s
if(!s)
{
printf("空间不足");//若无法生成结构体，则输出“空间不足”
return null;
}
else
{
s->top=-1; //初始栈顶为-1表示栈为空
s->sum=0;
return s;
}
}

3.3 判断栈空
int empty_seqstack(seqstack *s)
{
if (s->top==-1)
return 1; //栈顶为-1，表明栈为空
else
return 0;
}

3.4入栈
int push_seqstack(seqlist *l,int i,seqstack *s)
{
if(s->top==maxsize-1)
return 0; //栈满，无法入栈
else
{
s->top++;
s->data[s->top]=i; //顺序表中第i 个元素，i 入栈
s->sum=s->sum+l->data[i]; //栈中sum加和
return 1;
}
}

3.5出栈
int pop_seqstack(seqlist *l,seqstack *s,int *x)
{
if(empty_seqstack(s))
return 0; //栈空，无元素输出
else
{
*x=s->data[s->top]; //x指向栈顶元素
s->sum=s->sum-l->data[s->data[s->top]];//总和减去输出的栈顶元素值
s->top--; //栈内元素个数减1
return 1;
}
}
3.6输入元素
seqlist *init_seqlist()
{
seqlist *l; //定义一个顺序表指针变量
int x=1;
l=new seqlist; //动态生成一个顺序表
l->last=-1;
printf("-----------------\n请依次输入个物品的大小，输入0结束。\n------------------\n");
scanf("%d",&x); //格式化输入元素
while(x!=0) //输入元素不为0时，元素输入不结束
{
l->last++; //没输入一个元素，下标自增
l->data[l->last]=x;
scanf("%d",&x);
}
return l;
}
4调试与操作说明
输入背包体积n为15，各物体体积分别为1、2、3、4、5、6、7、8、9、10、11、12、13、14、15，输入完毕按0结束输入，运行结果如下：
图4-1 输入背包体积和物品体积

图4-2 可行的解
程序调试成功。
在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号，像“；”也很容易拉掉；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些毛病已经基本上克服了。在此过程中我学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。

总 结
通过此次课程设计的实践，感触较深。不仅使我加深了对书本知识的理解，而且锻炼了我编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计也充分弥补课堂教学及普通实验中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。
在本课题中，我们研究了如何用遗传算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， 其计算复杂度为，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及回溯法来解决普通的背包问题。我们可以看出在求解背包问题上显示了超出想象、良好的搜索能力，它具有收敛快、搜索速度快的特点，在试验中取得了比动态规划、遗传法和贪心法等更好的求解效果。然而在一般情况下，使用基本回溯算法解决背包问题时，得到问题的近似解也不能满足逼近最优解的要求。如何改进基本回溯算法使它所求得的解逼近最优解，成为我们当前亟待解决的问题，也是我们将来的学习中需要改进和加强的地方。
还有就是我们做的背包问题其实是整个背包问题的其中一支，本次的实验就做了其中的一种，其他的没有尝试，这是本次课程设计的遗憾之处。另外，就是本次课程设计的流程图也是不太完美，张亚红老师说我们设计的流程图在计算总体积T时如果不够返回在计算体现不出出栈的效果，但是我们确实设计不出更好的流程图来体现出栈，所以也算是其中的遗憾。

致 谢
一周的课程设计终于告与段落了，在这次课程设计的过程中，本人顺利完成了课程设计的大部分任务。在这其中，我也学会了很多东西所以要感谢那些在这其中帮助过我的人。
首先，要感谢淮阴工学院、计算机工程系能为我们提供这次课程设计的机会。正因为有了这次机会，才使得我们对数据结构有了更深的了解，并且能熟练掌握其中的一些算法设计等等，所以要感谢学校的精心安排。同时也要感谢实验室的工作人员，为我们提供了一个良好的实验环境，使我们能安心的完成课程设计的内容。在这期间我还要特别的感谢张亚红老师和张勇军老师，他们作为我们的知道老师，在他们的帮助下，我们可以很快的解决程序上的一些包括语法、逻辑算法、数据结构方面的问题，同时还学到了除本次课程设计以外的知识，如张亚红老师还跟我们提到了其他的一些数据结构的知识，其中包括线性表、树、图等等，是我获益匪浅。
我还要感谢我的同组成员彭建鑫同学。他和我一开始就明确分工，才开始我们一起找材料，然后一起商讨如何去实现这个设计。在编程的过程中，他又给与了我很大的帮助，有的如出栈的编程我不会的，他会帮助我一起完成。当编程结束的时候，我们却不能正常的运行，在他的帮助下，很顺利的找到了错误所在，然后就顺利的完成了背包问题求解这个设计。虽然这个设计看似简单，但对我们来说却是个不小的挑战，但我们还是战胜了挑战。
还有就是要感谢图书馆，它提供了大量的书籍供我们参考，也为我们本次课程设计提供了理论基础。

参考文献
1 苏仕华．数据结构课程设计．北京：机械工业出版社，2005
2 陈慧南．数据结构—C++语言描述．北京：人民邮电出版社，2005．03
3 严蔚敏，吴伟民．数据结构．北京：清华大学出版社，1997
4 王成端, 徐翠霞．数据结构上机实验与习题解析 北京-中国电力出版社，2006
5 Adam Drozdek．数据结构与算法，北京：清华大学出版社，2006
6 李春葆，金晶．数据结构教程．北京：清华大学出版社，2006
7 Mark Allen Weiss。Data structures and algorithm analysis in C++．北京：Posts & Telecom Press，2006
8 王红梅, 胡明, 王涛．数据结构 (C++版) 学习辅导与实验指导．北京：清华大学出版社，2005
9 胡元义．数据结构(C语言)实践教程．西安：西安电子科技大学出版社，2002
10 朱战立．数据结构－使用C++语言．西安：西安电子科技大学出版社，2001
11 周云静．数据结构习题解析与上机指导．北京：冶金工业出版社，2004
12 徐孝凯．数据结构实验．北京：中央广播电视大学出版社，2001
13 宁正元．数据结构习题解析与上机实验指导．北京：中国水利水电出版社，2000．9

指导教师评语
学号
1071304110
姓名
蒋为维
班级
网络107
选题
名称
背包问题求解
序号
评价内容
权重（%）
得分
1
考勤记录、学习态度、工作作风与表现。
5

2
自学情况：
上网检索机时数、文献阅读情况（笔记）。
10

3
论文选题是否先进，是否具有前沿性或前瞻性。
5

4
成果验收：
是否完成设计任务；能否运行、可操作性如何等。
20

5
报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。
30

6
文献引用是否合理、充分、真实。
5

7
答辩情况：
自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。
25

合计

指导教师（签章）：
2009 年 6 月 30 日