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

1、?数据结构?课程设计报告背包问题的求解学 院： 班 级： 学 号： 姓 名： 指导教师： 目 录1.需求分析 .3 2.概要设计 .53.详细设计 .7 4.调试分析 .10 5.用户使用说明 .10 6.测试结果 .117.附录 .14 2008年12月20日题目：背包问题的求解1、 程序的开始有个菜单栏目，可以选择程序来实现背包问题的求解。注：程序中 1：表示回溯遍历的可行性 2：反之表示不可行路径题目用到了两种方法来解决问题，分别是回溯法和递归法。2、 程序会建立简单背包问题的根本模型，背包的建立是在键盘上直接输入背包能容纳的最大重量、物品的个数和每个物品的重量的值的方法。在输入数据的过

2、程中，会提醒我们怎样输入数据，每一项数据输完后按Enter键进行下个数据项的输入。数据输入的结束会一直到简单背包问题模型的全部建立。3、主要功能：根据1中的选项程序会执行数组的加乘运算，并且会以排列的形式分别输出符合要求的所有可能组合及相关物品的相关信息.C会处理一些不符合矩阵加法和乘法运算的错误。4、栈与递归的实现：与汇编程序设计主程序和子程序之间的连接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的连接及信息交换需要通过站栈来进行。5、数据测试 在键盘上依次输入数字：“15 7 3 4 5 6 7 8 9运行结果为：背包能容纳的最大重量:15物品个数:7第1个物品重量:

3、3第2个物品重量:4第3个物品重量:5第4个物品重量:6第5个物品重量:7第6个物品重量:8第7个物品重量:9Result 1Item.4 Weight:6 Item.7 Weight:9Result 2Item.5 Weight:7 Item.6 Weight:8Result 3Item.1 Weight:3 Item.2 Weight:4 Item.6 Weight:8Result 4Item.1 Weight:3 Item.3 Weight:5 Item.5 Weight:7Result 5Item.2 Weight:4 Item.3 Weight:5 Item.4 Weight:6Pr

4、ess any key to continue如果输入不合法，编译系统将提示重新输入数据。输入数字“10 5 5 6 7 8 9运行结果为：运行结果为空值上面的数据测试是用数组法测得的。数据输入：15 7 3 4 5 6 7 8 9这次采用的快速编辑模式，上面数据是对数组元素和最值的取舍。运行结果：背包能容纳的最大重量:15物品个数:7第1个物品重量:3第2个物品重量:4第3个物品重量:5第4个物品重量:6第5个物品重量:7第6个物品重量:8第7个物品重量:9Result 1Item.4 Weight:6 Item.7 Weight:9Result 2Item.5 Weight:7 Item.

5、6 Weight:8Result 3Item.1 Weight:3 Item.2 Weight:4 Item.6 Weight:8Result 4Item.1 Weight:3 Item.3 Weight:5 Item.5 Weight:7Result 5Item.2 Weight:4 Item.3 Weight:5 Item.4 Weight:6Press any key to continue背包能容纳的最大重量：物品个数：第1个物品重量：第2个物品重量:第3个物品重量:第4个物品重量:第5个物品重量:第6个物品重量:第7个物品重量:背包能容纳的最大重量：15物品个数：7第1个物品重量：3

6、第2个物品重量：4第3个物品重量:5第4个物品重量:6第5个物品重量:7第6个物品重量:8第7个物品重量:9Press any key to continue一、type struct SElemType max; SElemType num;Sqstack;ADT Stack数据对象：D=ai|aiElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,i=2,n根本操作： InitStack(&S)操作结果：构造一个空串。 DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。 ClearStack(&S)初始条件：栈S毅存在。操作结果：将S清为空串

7、。 StackEmpty(S)初始条件：栈S已存在。操作结果：假设栈S为空串，那么返回不TRUE，否那么FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit()初始条件：栈S已存在且非空。操作结果：从站定到栈底依次对S的每个数据元素调用函数visit()

8、。一旦visit()失败，那么操作失败。ADT Stack二、据题目要求我定义了两个数组，用来记录数组中的每个物品的重量和标记每个物品是否被选中。int Item100=0假定物只对100个物品进行研究。int flag100=0;假定初始每个物品都未被选中标记。二、程序包含4个模块1、预处理命令和宏定义 1主函数模块void main ( )背包相关信息及物品相关信息变量的申明；输入输出操作的说明；模拟递归语句结构的声明； 建立操作菜单栏； 函数调用； 2Print函数的定义3循环语句的利用和声明3、函数的调用关系：主函数简单背包模型递归调用模块 循环模块程序包含5个模块 1、主函数模块 函

9、数变量的定义和申明；主函数的建立和调用 2、栈与递归的定义和说明 栈的定义和初始化；数组的运算 3、输入和输出模块对结果和时间复杂度的输入和输出； 4、运算模块进行加法运算，把结果给主函数 3、函数调用关系图主函数背包模型的建立递归标记模块 模拟栈模块输入输出模块三详细设计1、主函数的伪代码；for (int i=1;i=num;i+) if ( 0 = flagi ) flagi=1; continue; else flagi=0; break; 模拟递归.列举所有flag数组可能 。充分利用了栈与递归的实现。 其实就这个for循环是关键.实现程序处理问题的完备性和纯粹性。通过不断地更换物品

10、的标号来实现对所有函数返回值的递归遍历。 3、分析模块unsigned int count(0); unsigned int all_count(1); for (int i=1;i=num;i+) all_count*=2; /计算所有回溯递归遍历可能出现情况的种数。便于对算法的时空复杂度的分析作参考因素，有利于程序的课维护性。 初始化定义：unsigned int count(0); 初始计数器为0，即未对数组开始进行递归处理。unsigned int all_count(1);计数器目标初始化为1。通过幂分析来考虑算法的最大复杂度。实现编程的目的性较强。4、判断语句模块for (int

11、i=1;i=num;i+) if ( 1 = flagi ) temp+=itemi; 保证只对被标记选中的物品的重量进行计算求和使其到达背包的最大容量。并将求和结果带回主函数。4、while()循环语句结构。记录每次的求解情况。并输出函数结果 while (1) / 模拟递归.列举所有flag数组可能 / 其实就这个for循环是关键 for (int i=1;i=num;i+) if ( 0 = flagi ) flagi=1; continue; else flagi=0; break; /递归的内容在函数执行期间有效，并由编译器负责分配和收回。 / 把#if(0)改成#if(1)就可以了

12、 / 看看flag数组变化 / 在纸上画一下. / 应该很容易理解 / #if(0) for (int i=1;i=num;i+) coutflagi; coutendl; #endif / 判断时候装满背包 / 多加一个括号.使得临时变量每次重新创立而已 / 本次重量,初始化0 int temp(0); / 按标记计算所有选中物品(被标记)的重量之和 for (int i=1;i=num;i+) if ( 1 = flagi ) temp+=itemi; / 满足背包重量就打印 if ( temp = max ) resultCount+; Print(num); /调用Print函数 /

13、如果遍历了所有情况就break掉while(1)循环 count+; if (count=all_count) break; 便于分析算法的时间复杂度和运行效率。程序充分利用了栈与递归的实现。有效地节省存储空间，突出了算法的最优原那么。实用性较强。 1、用函数递归调用的方法:通过for语句和while 语句实现函数的回溯递归调用。用break和continue语句选择和判断程序的有机运行和函数的相关计算，使程序运行井然有序，创立良好的编译环境。提高代码的生成质量，便于结果的处理和分析。 2、鉴用网上的菜单式调用函数，修改了自己先得主函数调用方式，采用break()语句和continue语句。是

14、的程序看起来更简洁、明了，操作人性化。在以后的应用程序的开发中可以借鉴。3、程序的异常处理能力不是很强，只能判断根本变量运算法那么时弹出错误提示。对于多输入的“空格键或不是菜单栏的数字的选项没有异常处理机制。觉得是程序的一个缺乏、和以后提升的地方。4、在用函数调用用到了快速编辑模式，最后的结果看起来不是很清楚，直观。5、算法的时空分析。(1循环语句的时空分析如下： 程序结构体使用了数组item100，flag100，时间复杂度为o(n)+o(m)。把这num物品个数和num个标记常量转换到递归调用语句中并且输出这个的时间复杂度为2 num。最后分别遍历整个循环体，实现判断的时间复杂度为o(nu

15、m),输出结果的时间复杂度为o(num)。综上所述有总时间复杂度为：o(n)= 2num +num。循环体的空间的总复杂度为：o(s)=2num (2)该程序的时间复杂度主要表达在while和for语句的选择和判断的循环上，表现了循环语句的机动灵活性的特点，能有效地节省存储空间和代码的信息量。6、程序设计总结及感悟。发现自己对数据结果的很多的东西仅仅只有一个大概的了解，还不能应用到实际的编程中来，对C语言的运用不是很熟练，对函数的调用、文件的处理、动态内存的分配等知识有很大的缺乏。这个程序让我学会更多的东西，虽然这次没有把这些东西用上来，但是自己确实开始学会应用这些东西来解决问题。五,用户手册

16、本程序的运行环境适合于Windows操作系统。该程序代码较简洁，但程序运行效率较低，对于数量较少的变量进行处理比拟适宜。巧妙地利用标记数组flag对各个背包的是否利用情况实时判断处理，提高了程序的灵活性与随机应变能力，稳定性较强。数据的输入采用键盘直接输入的方法。在这个过程中输出界面会有详细的数据输入提示，已确保数据的正确输入。运行结果的输出一目了然，便于读者的理解。程序的可移植性较好，可用宇处理多种相关类似的问题。六、测试结果( 11、输入界面如下快速编辑模式：运行界面如下2、输入界面如下(常规编辑)：运行界面如下：3输入有错误时的一些情况。1、随机负荷超重取任意个物品重量之和均超过背包的最

17、大容量输入界面如下：运行界面如下：2、物品负荷失重所有物品重量小于背包最大容量输入界面如下：运行界面如下：3、背包相关输入参数数量不符合程序运行的要求(物品个数跟实际输入个数不符 )输入界面如下：运行界面：带注释的源程序。#include using namespace std; #define for if(1) for / 初始化每个物品的重量 int item100=0; / 标记数组 int flag100=0; / 结果计数器 int resultCount(0); / 打印结果 void Print(int num); int main() int max; int num; /

18、一开始打印一下条件 coutmax; coutnum; for (int i=1;i=num;i+) cout第i个物品重量:itemi; coutendl; / 所有可能性次数,即2的n次方 unsigned int count(0); unsigned int all_count(1); for (int i=1;i=num;i+) all_count*=2; /计算所有回溯遍历可能出现情况的种数 while (1) / 模拟递归.列举所有flag数组可能 / 其实就这个for循环是关键 for (int i=1;i=num;i+) if ( 0 = flagi ) flagi=1; continue; else flagi=0; break; for (int i=1;i=num;i+) coutflagi; coutendl; #endif / 判断时候装满背包 / 多加一个括号.使得临时变量每次重新创立而已 / 本次重量,初始化0 int temp(0); / 按标记计算所有选中物品(被标记)的重量之和 for (int i=1;i=num;i+) if ( 1 = flagi ) temp+=item