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

1、背包問題 實驗題目：背包問題 問題描述：假設有一個能裝入總體積為 T 的背包和 n 件體積分別為 w 1, w 2,w n 的物品，能否從 n 件物品中挑選若干件恰好裝滿背包，即使 w 1+w 2+ + w n=T,要求找出所有滿足上述條件的解。 例如：當T=10,各件物品的體積1, 8, 4, 3, 5, 2時，可找到下列4組 解： （ 1， 4， 3， 2） （1, 4, 5） （ 8, 2） （ 3, 5, 2）。 概要設計： 采用棧數據結構,利用回溯法的設計思想來解決背包問題。 首先將物品排成一列，然后順序選取物品裝入背包，假設已選取了前i 件物 品之后背包還沒有裝滿，則繼續(xù)選取第 i

2、+1 件物品，若該件物品 “太大”不能裝 入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找 不到合適的物品以填滿背包，則說明 “剛剛”裝入背包的那件物品 “不合適 ”，應將 它取出 “棄之一邊 ”，繼續(xù)再從 “它之后”的物品中選取，如此重復，直至求得滿足 條件的解，或者無解。 ADT Stack 數據對象：D= ai | ai ElemSet, i=1,2，,n, n0 數據關系：R1 = | ai-1, ai D, i=2,n 約定 an 端為棧頂， a1 端為棧底。 基本操作： InitStack(/fp1 指向數據文件， fp2 指向結果文件 typedef stru

3、ct SqStack int *base; int *top; int num; SqStack; struct SqStack *S,L; int InitStack(SqStack *s,int n) s-base=(int *)malloc(n*sizeof(int); if(!s-base) exit(0); s-top=s-base; s-num=0; return OK; / 創(chuàng)建棧 int Push(SqStack *s,int m) *s-top+=m; s-num+; return OK; / 元素入棧 int Pop(SqStack *s,int *p) if(s-base

4、=s-top)return 0; -s-top; *p=*s-top; s-num-; return OK; /元素出棧，用指針p返回 int print(SqStack *s,int w) int *p; p=s-base; while(ptop) fprintf(fp2,%d ,w*p); printf(%d ,w*p); p+; fprintf(fp2,n); printf(n); return OK; / 把棧中元素在文件中輸出和在屏幕上輸出 int StackEmpty(SqStack *s) if(s-base=s-top) return 0; else return 1; / 棧

5、是否為空 void knapsack (int w,int T,int n) /已知n件物品的體積分別為w0, w1, wn，背包的總體積為T,/本算 法輸出所有恰好能裝滿背包的物品組合解 int k=0;/ 從第 0 件物品考察起 int pint=0;/ 計算輸出結果組數，如果沒有，則提示無結果 int *pk= S= InitStack(S,n); do if(Pop(S,pk)退出棧頂物品 T+=wk; k+;/ 繼續(xù)考察下一件物品 while(T0 T-=wk; k+;/ 繼續(xù)考察下一件物品 if(T=0) print(S,w); pint+; / 輸出第一組解 while (Sta

6、ckEmpty(S)/while if(!pint) fprintf(fp2, 未找”到匹配結果 ” ); printf( 未“找到匹配結果 ” ); / knapsack int main(int argc,char *argv) 輸出文件名） / 命令輸入為： (可執(zhí)行文件名)(輸入文件名) / 例如： beibao shuju.txt jieguo.txt /shuju.txt 文件中輸入為： T n w1 w2 . wn int i,n,T; int aN; if(fp1=fopen(argv1,r)=NULL) printf( 文件未找到，請創(chuàng)建并輸入 :); exit(0); if

7、(fp2=fopen(argv2,w)=NULL) printf( 創(chuàng)建文件失敗 ); exit(0); fscanf(fp1,%d%d, for(i=0;in;i+) fscanf(fp1,%d,/ 從文件中讀入數據 knapsack(a,T,n); fclose(fp1); fclose(fp2); /* * beibao.c * *Created on: 2009-10-23 *Author: PB08210347 */ 數據檢測及結果： 在命令行中輸入： beibao shuju.txt jieguo.txt 結果如下圖所示： 命令行執(zhí)行： 數據文件： 結果文件： 調試過程及分析： 調

8、試前，把一些語法等錯誤清楚后，發(fā)現沒有輸出運行結果。之后進行調 試。調試時發(fā)現如下問題： 1、 ?？盏暮瘮捣祷刂蹬c調用時的值運用錯誤。導致在kn apsack函數中的循 環(huán)循環(huán)一次就退出來了。因此，這種錯誤值得注意。 2、接著，發(fā)現第一個循環(huán) while 不能先判斷條件，而只需先做再判斷條 件。之后就改為 do,while 循環(huán)。 3、調試時，發(fā)現對棧中的元素個數不能清楚地看到，因此在棧的結構體中 加入了一個 num 域。這樣，調試時對棧就能清楚的了解其中入站和出站的過 程。 4、后來發(fā)現運行只出現了三組結果。繼續(xù)考察，調試，其中，輸出三組結 果后，循環(huán)跳出來了。原來棧中的元素已經為空，即在新的元素入棧前，棧已 為空，于是，將 P