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

背包问题数据结构实验报告
背包问题数据结构实验报告
背包问题数据结构实验报告
淮阴工学院
数据结构课程设计报告
⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
.⋯ 6

的初始化 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
.⋯⋯⋯ 7

判断 空 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
.⋯⋯⋯⋯ 7

入 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
.⋯⋯⋯⋯ 7

出 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
.⋯⋯⋯⋯ 8

入元素 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
.⋯⋯⋯⋯ 8
4 与操作 明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ..⋯⋯⋯ 9
5 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ .⋯⋯⋯ 11
6 致 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ .⋯⋯ 12
背包问题数据结构实验报告
背包问题数据结构实验报告
背包问题数据结构实验报告
7 参照文件 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ .⋯⋯⋯ 13
背包问题数据结构实验报告
背包问题数据结构实验报告
背包问题数据结构实验报告
需求剖析
本课程设计（实践周）题目
假 有一个能装入 体 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
目 函数： max
f ( x1 , x2
, xn )
ci xi
i 1
n

wi xi
pi
（* ）
i 1
xi
{ 0,1}
(i
1,2, n)
式中 xi 0-1
决议 量， xi
1
表示将物件 i 装入背包中， xi
0 表示
不将其装入背包中。
课程设计（实践周）任务及要求
方面的 料；
，我 数据 构， 写代 ；彭建鑫 流程 和回
溯法介
程 告；
。
课程设计（实践周）思想
利用回溯法的 思想来解决背包 。第一将物件摆列成一列，而后
背包问题数据结构实验报告
背包问题数据结构实验报告
背包问题数据结构实验报告
1
背包问题数据结构实验报告
背包问题数据结构实验报告
背包问题数据结构实验报告
次序选用物件装入背包，假定已选用了前 i 件物件后背包还没装满，则持续选用第 i+1 件物件，若该件物件 “太大 ”不可以装入，则弃之而选用下一件，直到背包装满为止。 但假如在节余的物件中找不到适合的物件以填满背包， 则说明 “刚才 ”装入背包的那见物件 “不适合 ”，应当将它去出 “弃之一边 ”，持续再从 “它以后 ”的物件中选用， 这样重复，直到求得知足条件的解， 或许无解。因为回溯法求解的规则是 “后进先出 ”所以自然要用到栈。
软硬件运转环境及开发工具
Windows2000 以上操作系统
Visual C++ 以上编译环境
纲要设计
本课题设计所用数据结构以及流程图
栈的原理
作为组长，我主假如负责该部分。 背包问题求解波及到的数据结构主假如栈，下边我就详尽的介绍一下相关栈方面的知识。
栈（ Stack）是限制仅在表的一端进行插入和删除运算的线性表。当用一维数组储存栈时，被称为次序栈。
(1)往常称插入、删除的这一端为栈顶 （Top），另一端称为栈底（Bottom）；
(2)当表中没有元素时称为空栈，用 Top==-1 表示；
(3)栈为后进先出（ Last In Fir