背包问题分析和总结.docxVIP

课程 设计报告

课程名称 数据结构课程设计课题名称 背包问题

专

业

信息与计算科学

班

级

1001班

学

号

22

姓

名

王锐

指导教师 刘洞波 张晓清 郭芳

2012年6月9日

1

课程设计任务书

课程名称 数据结构课程设计课 题 背包问题

专业班级 信科1001班学生姓名 王锐

学 号 22

指导老师 刘洞波 张晓清 郭芳

审 批 刘洞波 张晓清 郭芳

任务书下达日期： 2012年6月9日

任务完成日期： 2012年6月16日

2

PAGE

PAGE10

、设计内容与设计要求1．设计内容：

问题描述

假设有一个能装入总体积为T的背包和n件体积分别为W1，W2，···，Wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使W1+W2+···+Wn=T，要求找出所有满足上述条件的解。例如：当T=10，共6件物品，物品的体积为{1，2，3，4，5，8}，那么可找到下列4组解：（1，2，3，4）、（1，4，5）、（2，3，5）、（2、8）。

实现提示

可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则丢弃而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“丢弃一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。

由于回溯求解的规则是“后进先出”，因此要用到栈。

设计要求：

课程设计报告规范

需求分析

程序的功能。

输入输出的要求。

概要设计

程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。

详细设计

采用C语言定义相关的数据类型。

写出各模块的类C码算法。

画出各函数的调用关系图、主要函数的流程图。

调试分析以及设计体会

测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

程序调试中遇到的问题以及解决问题的方法。

课程设计过程经验教训、心得体会。

使用说明

用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。

书写格式

见附带说明。

附录

参考书目

源程序清单（带注释）

考核方式

指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：

①平时出勤（占10%）

②系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）

③程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）

④设计报告（占30%）

注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。

⑤独立完成情况（占10%）。

课程验收要求

①运行所设计的系统。

②回答有关问题。

③提交课程设计报告。

④提交软盘（源程序、设计报告文档）。

⑤依内容的创新程度，完善程序情况及对程序讲解情况打分。

二、进度安排

周二上午

周二上午8:00-12:00周三下午14:30-18:30

周四上午8:00-12:00

E410/411E513

E513

附：

课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。

正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。

目录

1.需求分析……………………

1.1程序功能……………….

1.2输入输出要求………….

2.概要设计……………………

2.1主要程序功能模块图…………………

2.2数据结构及其关系……………………

3.详细设计……………………

3.1C语言定义的相关数据类型……………