背包問題實驗報告(C語言實現(xiàn)、文件輸入及文件輸出)

背包問題實驗題目：背包問題問題描述：假設有一個能裝入總體積為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）。概要設計：采用棧數(shù)據(jù)結構，利用回溯法的設計思想來解決背包問題。首先將物品排成一列，然后順序選取物品裝入背包，假設已選取了前i件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入背包的那件物品“不合適”，應將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復，直至求得滿足條件的解，或者無解。ADTStack{數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底?；静僮鳎篒nitStack(&S)操作結果：構造一個空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結果：棧S被銷毀。ClearStack(&S)初始條件：棧S已存在。操作結果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。操作結果：若棧S為空棧，則返回TRUE，否則FALSE。StackLength(S)初始條件：棧S已存在。操作結果：返回S的元素個數(shù)，即棧的長度。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指向數(shù)據(jù)文件，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;}//創(chuàng)建棧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;//計算輸出結果組數(shù)，如果沒有，則提示無結果int*pk=&k; S=&L;InitStack(S,n);do{if(Pop(S,pk)){//退出棧頂物品T+=w[k];k++;//繼續(xù)考察下一件物品 } while(T>0&&k<n){if(T-w[k]>=0){//第k件物品可選，則k入棧Push(S,k);T-=w[k];}k++;//繼續(xù)考察下一件物品 if(T==0){print(S,w); pint++;}//輸出第一組解 } } while((StackEmpty(S))&&(k<=n));//while if(!pint){ fprintf(fp2,”未找到匹配結果”); printf(“未找到匹配結果”); }}//knapsackintmain(intargc,char*argv[]){ //命令輸入為：(可執(zhí)行文件名）（輸入文件名）（輸出文件名） //例如：beibaoshuju.txtjieguo.txt //shuju.txt文件中輸入為：Tnw1w2...wn inti,n,T; inta[N]; if((fp1=fopen(argv[1],"r"))==NULL){ printf("文件未找到，請創(chuàng)建并輸入:"); exit(0); } if((fp2=fopen(argv[2],"w"))==NULL){ printf("創(chuàng)建文件失敗"); exit(0); } fscanf(fp1,"%d%d",&T,&n); for(i=0;i<n;i++){ fscanf(fp1,"%d",&a[i]);//從文件中讀入數(shù)據(jù) } knapsack(a,T,n); fclose(fp1); fclose(fp2);}/**beibao.c**Createdon:2009-10-23*Author:PB08210347*/數(shù)據(jù)檢測及結果：在命令行中輸入：beibaoshuju.txtjieguo.txt結果如下圖所示：命令行執(zhí)行：數(shù)據(jù)文件：結果文件：調試過程及分析：調試前，把一些語法等錯誤清楚后，發(fā)現(xiàn)沒有輸出運行結果。之后進行調試。調試時發(fā)現(xiàn)如下問題：?？盏暮瘮?shù)返回值與調用時的值運用錯誤。導致在knapsack函數(shù)中的循環(huán)循環(huán)一次就退出來了。因此，這種錯誤值得注意。接著，發(fā)現(xiàn)第一個循環(huán)while不能先判斷條件，而只需先做再判斷條件。之后就改為do……while循環(huán)。調試時，發(fā)現(xiàn)對棧中的元素個數(shù)不能清楚地看到，因此在棧的結構體中加入了一個num域。這樣，調試時對棧就能清楚的了解其中入站和出站的過程。后來發(fā)現(xiàn)運行只出現(xiàn)了三組結果。繼續(xù)考察，調試，其中，輸出三組結果后，循環(huán)跳出來了。原來棧中的元素已經為空，即在新的元素入棧前，棧已為空