背包问题实验报告(C语言实现、文件输入及文件输出).pdf

该【背包问题实验报告(C语言实现、文件输入及文件输出) 】是由【青山代下】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【背包问题实验报告(C语言实现、文件输入及文件输出) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。背包问题实验题目:背包问题问题描述:假设有一个能装入总体积为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)。概要设计:采用栈数据结构,利用回溯法的设计思想来解决背包问题。首先将物品排成一列,然后顺序选取物品装入背包,假设已选取了前i件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品“太大”不能装入,则弃之而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入背包的那件物品“不合适”,应将它取出“弃之一边”,继续从再“它之后”的物品中选取,如此重复,直至求得满足条件的解,或者无解。ADTStack{1/9数据对象:D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作:InitStack(&S)操作结果:构造一个空栈S。DestroyStack(&S)初始条件:栈S已存在。操作结果:栈S被销毁。ClearStack(&S)初始条件:栈S已存在。操作结果:将S清为空栈。StackEmpty(S)初始条件:栈S已存在。操作结果:若栈S为空栈,则返回TRUE,否则FALSE。StackLength(S)初始条件:栈S已存在。操作结果:返回S的元素个数,即栈的长度。GetTop(S,&e)初始条件:栈S已存在且非空。2/9操作结果:用e返回S的栈顶元素。Push(&S,e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。Pop(&S,&e)初始条件:栈S已存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。}ADTStack源代码:#include<>#include<>#include<>#include<>#defineOK1#defineN20FILE*fp1,*fp2;//fp1指向数据文件,fp2指向结果文件typedefstructSqStack{int*base;int*top;intnum;}SqStack;structSqStack*S,L;3/9intInitStack(SqStack*s,intn){s->base=(int*)malloc(n*sizeof(int));if(!s->base)exit(0);s->top=s->base;s->num=0;returnOK;}//创建栈intPush(SqStack*s,intm){*s->top++=m;s->num++;returnOK;}//元素入栈intPop(SqStack*s,int*p){if(s->base==s->top)return0;--s->top;*p=*s->top;s->num--;returnOK;}//元素出栈,用指针p返回intprint(SqStack*s,intw[]){int*p;4/9p=s->base;while(p<s->top){p++;}returnOK;}//把栈中元素在文件中输出和在屏幕上输出intStackEmpty(SqStack*s){if(s->base==s->top)return0;elsereturn1;}//栈是否为空voidknapsack(intw[],intT,intn){//已知n件物品的体积分别为w[0],w[1],?,w[n],背包的总体积为T,//本算法输出所有恰好能装满背包的物品组合解intk=0;//从第0件物品考察起intpint=0;//计算输出结果组数,如果没有,则提示无结果int*pk=&k;S=&L;InitStack(S,n);5/9do{if(Pop(S,pk)){//退出栈顶物品T+=w[k];k++;//继续考察下一件物品}while(T>0&&k<n){if(T-w[k]>=0){//第k件物品可选,则k入栈Push(S,k);T-=w[k];}k++;//继续考察下一件物品if(T==0){print(S,w);pint++;}//输出第一组解}}while((StackEmpty(S))&&(k<=n));//whileif(!pint){fprintf(fp2,”未找到匹配结果”);printf(“未找到匹配结果”);6/9}}//knapsackintmain(intargc,char*argv[]){//命令输入为:(可执行文件名)(输入文件名)(输出文件名)//例如://:Tnw1w2...wninti,n,T;inta[N];文件未找到,请创建并输入exit(0);}创建文件失败exit(0);}for(i=0;i<n;i++){从文件中读入数据}knapsack(a,T,n);7/9fclose(fp1);fclose(fp2);}/****Createdon:2009-10-23*Author:PB08210347*/数据检测及结果:在命令行中输入::命令行执行:数据文件:结果文件:调试过程及分析:调试前,把一些语法等错误清楚后,发现没有输出运行结果。之后进行调试。调试时发现如下问题:1、栈空的函数返回值与调用时的值运用错误。导致在knapsack函数中的循环循环一次就退出来了。因此,这种错误值得注意。2、接着,发现第一个循环while不能先判断条件,而只需先做再判断条件。之后就改为do??while循环。8/93、调试时,发现对栈中的元素个数不能清楚地看到,因此在栈的结构体中加入了一个num域。这样,调试时对栈就能清楚的了解其中入站和出站的过程。4、后来发现运行只出现了三组结果。继续考察,调试,其中,输出三组结果后,循环跳出来了。原来栈中的元素已经为空,即在新的元素入栈前,栈已为空,于是,将Pop(S,pk)//退出栈顶物品T+=w[k];k++;//继续考察下一件物品提到循环最前面,并加上判断的if。这样才输出了正确结果。5、最后,把程序中的一些小环节加以注释,还有把没有匹配的要提示。从而使程序更好的使用,使其更健壮,更完善。9/9