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

淮阴工学院

数据结构课程设计报告

选题名称: 背包问题求解系（院）: 计算机工程系

专 业: 计算机科学与技术班 级: 网络107

姓 名: 蒋为维 学 号:指导教师: 张亚红 张勇军

学年学期: 2008~2009 学年第 2 学期

2009 年 6 月 20 日

设计任务书

1

2009.06.08

理论辅导，搜集资料

2

2009.06.08~2009.06.10

编写代码，上机调试

3

2009.06.11

撰写课程设计报告

4

2009.06.12

答辩

课题名称

课题

名称

背包问题求解

通过一周的课程设计，实现回溯法解决背包问题的方法，达到巩固理论知

设计

目的

识、锻炼实践能力、构建合理知识结构的目的。

实验

环境

Windows2000以上操作系统VisualC++6.0以上编译环境

搜集背包问题方面的资料；

编写代码，实现回溯法背包问题；

任务

要求

3.

撰写课程设计报告；

4. 参加答辩；

工作进度计划

序号

起止日期

工 作 内 容

指导教师：

2009

年 6

月

10

日

任务书格式参照“任务书范例”执行。

范例中的红．色．文字应根据你所选择的具体课题，修改为对应的内容。范例中的其它内容不变。

摘要：

组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。背包问题是一个典型

的组合优化问题，在计算理论中属于NP-完全问题，其计算复杂度为O(2n)，传统上采用动态规划来求解。设w[i]是经营活动i所需要的资源消耗，M是所能提供的资源总量，p[i]是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。

关键词：背包问题，堆栈，回溯法，递归

目 录

需求分析 1

课程设计（实践周）题目 1

课程设计（实践周）任务及要求 1

课程设计（实践周）思想 1

软硬件运行环境及开发工具 2

概要设计 2

本课题设计所用数据结构以及流程图 2

栈的原理 2

溯法介绍 3

包问题整体流程图 5

本课题主要设计思想 6

代码设计 6

定义栈和顺序表结构体 6

栈的初始化 7

判断栈空 7

入栈 7

出栈 8

输入元素 8

调试与操作说明 9

5总结 11

6致谢 12

7参考文献 13

PAGE

PAGE1

需求分析

本课程设计（实践周）题目

假设有一个能装入总体积为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整数规划模型：

目标函数：

max f(x,x

1 2

?,x

n

)??n cx

i i

i?1

?

?s.t?

?

? wx ?p

ni i i

n

（*）

??x?{i?01,1} (i?1,2,?n)

?

i

式中x为0-1决策变量，x ?1时表示将物品i装入背包中，x ?0时则表示

i i i

不将其装入背包中。

课程设计（实践周）任务及要求

搜集背包问题方面的资料；

作为组长，我负责设计数据结构，编写代码；彭建鑫设计流程图和回溯法介绍

撰写课程设计报告；

参加答辩。

课程设计（实践周）思想

利用回溯法的设计思想来解决背包问题。首先将物品排列成一列，然后

顺序选取物品装入背包，假设已选取了前i件物品后背包还没装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而选取下一件，直到背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那见物品“不合适”，应该将它去出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯法求解的规则是“后进先出”因此自然要用到栈。

软硬件运行环境及开发工具

Windows2000以上操作系统VisualC++6.0以上编译环境

概要设计

本课题设计所用数据结构以及流程图

栈的原理

作为组长，我主要是负责