背包问题实验报告(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 件物 品之后背包还没有装满，则继续选取第 i

2、+1 件物品，若该件物品 “太大”不能装 入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找 不到合适的物品以填满背包，则说明 “刚刚”装入背包的那件物品 “不合适 ”，应将 它取出 “弃之一边 ”，继续再从 “它之后”的物品中选取，如此重复，直至求得满足 条件的解，或者无解。 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; / 创建栈 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+;/ 继续考察下一件物品 while(T0 T-=wk; k+;/ 继续考察下一件物品 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) 输出文件名） / 命令输入为： (可执行文件名)(输入文件名) / 例如： 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( 文件未找到，请创建并输入 :); exit(0); if

7、(fp2=fopen(argv2,w)=NULL) printf( 创建文件失败 ); 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 结果如下图所示： 命令行执行： 数据文件： 结果文件： 调试过程及分析： 调

8、试前，把一些语法等错误清楚后，发现没有输出运行结果。之后进行调 试。调试时发现如下问题： 1、 栈空的函数返回值与调用时的值运用错误。导致在kn apsack函数中的循 环循环一次就退出来了。因此，这种错误值得注意。 2、接着，发现第一个循环 while 不能先判断条件，而只需先做再判断条 件。之后就改为 do,while 循环。 3、调试时，发现对栈中的元素个数不能清楚地看到，因此在栈的结构体中 加入了一个 num 域。这样，调试时对栈就能清楚的了解其中入站和出站的过 程。 4、后来发现运行只出现了三组结果。继续考察，调试，其中，输出三组结 果后，循环跳出来了。原来栈中的元素已经为空，即在新的元素入栈前，栈已 为空，于是，将 P