背包問(wèn)題實(shí)驗(yàn)報(bào)告

背包問(wèn)題實(shí)驗(yàn)題目：背包問(wèn)題問(wèn)題描述：假設(shè)有一個(gè)能裝入總體積為T(mén)的背包和n件體積分別為w1,w2,...,wn的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1+w2+...+wn=T,要求找出所有滿足上述條件的解。例如：當(dāng)T=10,各件物品的體積｛1,8,4,3,5,2｝時(shí)，可找到下列4組解：（1,4,3,2)(1,4,5)(8,2)(3,5,2)o概要設(shè)計(jì)：采用棧數(shù)據(jù)結(jié)構(gòu)，利用回溯法的設(shè)計(jì)思想來(lái)解決背包問(wèn)題。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i件物品之后背包還沒(méi)有裝滿，則繼續(xù)選取第i+1件物品，若該件物品〃太大〃不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說(shuō)明〃剛剛〃裝入背包的那件物品"不合適〃，應(yīng)將它取出"棄之一邊〃，繼續(xù)再?gòu)摹ㄋ蟆ǖ奈锲分羞x取，如此重復(fù)，直至求得滿足條件的解，或者無(wú)解。ADTStack｛數(shù)據(jù)對(duì)象：D={ai|ai^ElemSet,i=l,2,...,n,n>0}數(shù)據(jù)關(guān)系：Rl={<ai-l,ai>|ai-1,aiCD,i=2,...,n}約定an端為棧頂，al端為棧底?；静僮鳎簂nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷(xiāo)毀。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若棧S為空棧，則返回TRUE,否則FALSEoStackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。GetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}ADTStack源代碼：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<malloc.h>#defineOK1#defineN20FILE*fpl,*fp2;//fpl指向數(shù)據(jù)文件,fp2指向結(jié)果文件typedefstructSqStack{int*base;int*top;intnum;}SqStack;structSqStack*S,L;intlnitStack(SqStack*s,intn){s->base=(int*)malloc(n*sizeof(int));if(!s->base)exit(O);s->top=s->base;sonum=0;returnOK;}〃創(chuàng)建棧intPush(SqStack*s,intm){*s->top++=m;sonum++;returnOK;}〃元素入棧intPop(SqStack*s,int*p){if(s->base==s->top)return0;-s->top;*p=*s->top;sonum-;returnOK;}〃元素出棧,用指針p返回intprint(SqStack*s,intw[]){int*p;p=s->base;while(p<s->top){fprintf(fp2,"%d",w[*p]);printf("%dn,w[*p]);P++；}fprintf(fp2八n“);printfCAn");returnOK;}〃把棧中元素在文件中輸出和在屏幕上輸出intStackEmpty(SqStack*s){if(s->base==s->top)return0;elsereturn1;}〃棧是否為空voidknapsack(intw[],intT,intn){〃已知n件物品的體積分別為w[0], w[n],背包的總體積為「〃本算法輸出所有恰好能裝滿背包的物品組合解intk二0;//從第0件物品考察起intpint=O;//計(jì)算輸出結(jié)果組數(shù)，如果沒(méi)有，則提示無(wú)結(jié)果int*pk=&k;S二&L;lnitStack(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==O){print(S,w);pint++;}〃輸出第一組解}}while((StackEmpty(S))&&(k<=n));//whileif(!pint){fprintf(fp2/?未找到匹配結(jié)果〃)；printf(“未找到匹配結(jié)果〃)；}//knapsackintmain(intargc,char*argv[]){〃命令輸入為：(可執(zhí)行文件名)(輸入文件名)(輸出文件名)〃例如：beibaoshuju.txtjieguo.txt//shuju.txt文件中輸入為：Tnwlw2...wninti,n,T;inta[N];if((fpl=fopen(argv[l]/'r"))==NULL){printff"文件未找到，請(qǐng)創(chuàng)建并輸入:”)；exit(O);}if((fp2=fopen(argv[2],"w"))==NULL){printf(H創(chuàng)建文件失敗“)；exit(O);}fscanf(fpl,"%d%d",&T,&n);for(i=0;ivn;i++){fscanf(fpb“％d“,&a[i]);〃從文件中讀入數(shù)據(jù)}knapsack(a,T,n);fclose(fpl);fclose(fp2);beibao.c**Createdon:2009-10-23?Author:PB08210347*/數(shù)據(jù)檢測(cè)及結(jié)果：在命令行中輸入:beibaoshuju.txtjieguo.txt結(jié)果如下圖所示：命令行執(zhí)行：數(shù)據(jù)文件：結(jié)果文件：調(diào)試過(guò)程及分析：調(diào)試前，把一些語(yǔ)法等錯(cuò)誤清楚后，發(fā)現(xiàn)沒(méi)有輸出運(yùn)行結(jié)果。之后進(jìn)行調(diào)試。調(diào)試時(shí)發(fā)現(xiàn)如下問(wèn)題：1、 ?？盏暮瘮?shù)返回值與調(diào)用時(shí)的值運(yùn)用錯(cuò)誤。導(dǎo)致在knapsack函數(shù)中的循環(huán)循環(huán)一次就退出來(lái)了。因此，這種錯(cuò)誤值得注意。2、 接著，發(fā)現(xiàn)第一個(gè)循環(huán)while不能先判斷條件，而只需先做再判斷條件。之后就改為do〃〃while循環(huán)。3、 調(diào)試時(shí)，發(fā)現(xiàn)對(duì)棧中的元素個(gè)數(shù)不能清楚地看到，因此在棧的結(jié)構(gòu)體中加入了一個(gè)num域。這樣，調(diào)試時(shí)對(duì)棧就能清楚的了解其中入站和出站的過(guò)程。4、 后來(lái)發(fā)現(xiàn)運(yùn)行只出現(xiàn)了三組結(jié)果。繼續(xù)考察，調(diào)試，其中，輸出三組結(jié)果后，循環(huán)跳出來(lái)了。原來(lái)?xiàng)?/p>