背包问题实验报告(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{数据对象：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已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack源代码：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<malloc.h>#defineOK1#defineN20FILE*fp1,*fp2;//fp1指向数据文件，fp2指向结果文件typedefstructSqStack{ int*base; int*top; intnum;}SqStack;structSqStack*S,L;intInitStack(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; p=s->base; while(p<s->top){ fprintf(fp2,"%d",w[*p]); printf("%d",w[*p]); p++; } fprintf(fp2,"\n"); printf("\n"); 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);do{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));//while if(!pint){ fprintf(fp2,”未找到匹配结果”); printf(“未找到匹配结果”); }}//knapsackintmain(intargc,char*argv[]){ //命令输入为：(可执行文件名）（输入文件名）（输出文件名） //例如：beibaoshuju.txtjieguo.txt //shuju.txt文件中输入为：Tnw1w2...wn inti,n,T; inta[N]; if((fp1=fopen(argv[1],"r"))==NULL){ printf("文件未找到，请创建并输入:"); exit(0); } if((fp2=fopen(argv[2],"w"))==NULL){ printf("创建文件失败"); exit(0); } fscanf(fp1,"%d%d",&T,&n); for(i=0;i<n;i++){ fscanf(fp1,"%d",&a[i]);//从文件中读入数据 } knapsack(a,T,n); fclose(fp1); fclose(fp2);}/**beibao.c**Createdon:2009-10-23*Author:PB08210347*/数据检测及结果：在命令行中输入：beibaoshuju.txtjieguo.txt结果如下图所示：命令行执行：数据文件：结果文件：调试过程及分析：调试前，把一些语法等错误清楚后，发现没有输出运行结果。之后进行调试。调试时发现如下问题：栈空的函数返回值与调用时的值运用错误。导致在knapsack函数中的循环循环一次就退出来了。因此，这种错误值得注意。接着，发现第一个循环while不能先判断条件，而只需先做再判断条件。之后就改为do……while循环。调试时，发现对栈中的元素个数不能清楚地看到，因此在栈的结构体中加入了一个num域。这样，调试时对栈就能清楚的了解其中入站和出站的过程。后来发现运行只出现了三组结果。继续考察，调试，其中，输出三组结果后，循环跳出来了。原来栈中的元素已经为空，即在新的元素入栈前，栈已为空