背包问题数据结构实验报告(共18页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
淮阴工学院
数据结构课程设计报告
选题…………………………….…………7
…………………………………………………………………….…………8
……………………………………………………………….…………8
4调试与操作说明……………………………………..………9
5总结………………………………………………….………11
6致谢…………………………………………………….……12
7参考文献…………………………………………….………13
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
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决策变量，时表示将物品装入背包中，时则表示不将其装入背包中。
（实践周）任务及要求
；
，我负责设计数据结构，编写代码；彭建鑫设计流程图和回溯法介绍
；
。
（实践周）思想
利用回溯法的设计思想来解决背包问题。首先将物品排列成一列，然后顺序选取物品装入背包，假设已选取了前i件物品后背包还没装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而选取下一件，直到背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那见物品“不合适”，应该将它去出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯法求解的规则是“后进先出”因此自然要用到栈。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业

Windows2000以上操作系统
Visual C++
2概要设计
本课题设计所用数据结构以及流程图

作为组长，我主要是负责该部分。背包问题求解涉及到的数据结构主要是栈，下面我就详细的介绍一下有关栈方面的知识。
栈（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）Stack