背包问题实验报告(C语言实现、文件输入及文件输出)
- 格式：docx
- 大小：13.94 KB
- 文档页数：9
背包问题
假设有一个能装入总体积为
T 的背包和n 件体积分别为W
能否从 n 件物品中挑选若干件恰好装满背包,即使 W
1+w
2+ …+ W
n=T ,要求找出所有满足上述条件的解。
T=10,各件物品的体积｛1, 8, 4, 3, 5, 2｝时，可找到下列4组
3， 2)
概要设计：
采用栈数据结构，利用回溯法的设计思想来解决背包问题。
首先将物品排成一列,然后顺序选取物品装入背包,假设已选取了前 i 件物 品之后背包还没有装满,则继续选取第 i+1 件物品,若该件物品 “太大”不能装 入,则弃之而继续选取下一件,直至背包装满为止。
但如果在剩余的物品中找 不到合适的物品以填满背包,则说明 “刚刚”装入背包的那件物品 “不合适”,应将 它取出“弃之一边”,继续再从 “它之后”的物品中选取,如此重复,直至求得满足 条件的解,或者无解。
ADT Stack {
数据对象：D = { ai | ai € ElemSet, i=1,2,…,n.
n A 0 }
背包问题
1, w 2, … , W
1， 4，
5) 8， 2) 3， 5， 2)。
n 的物品， 例如：当 解：( 1 , 4，
数据关系：R1 = { vai-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返回其值。
} ADT Stack
源代码：
#include<stdio.h> #include<stdlib.h> #include<math.h>
#include<malloc.h> #define OK 1 #define N 20
FILE *fp1,*fp2;//fp1 指向数据文件，fp2 指向结果文件
typedef struct 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==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(p<s->top){
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;
}// 栈是否为空
void knapsack (int w[],int T,int n) {
//已知n件物品的体积分别为w[0], w[1],,, w[n]，背包的总体积为T,//本算法输出所有恰好能装满背包的物品组合解
int k=0;// 从第0件物品考察起
int pint=0;// 计算输出结果组数，如果没有，则提示无结果
int *pk=&k;
S=&L;
InitStack(S,n);
do{
if(Pop (S ,p k)){//退出栈顶物品
T+=w[k];
k++;//继续考察下一件物品
while(T>0&&k<n){
if （T-w[k]>=0） {//第k件物品可选，则k入栈Push(S,k);
T-=w[k];
k++;//继续考察下一件物品
print(S,w);
pint++;
}// 输出第一组解
while ((StackEmpty(S))&&(k<=n));//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 a[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
*Created on: 2009-10-23
*Author: PB08210347
*/
数据检测及结果：
在命令行中输入：beibao shuju.txt jieguo.txt
结果如下图所示：
命令行执行：
数据文件：
结果文件：
调试过程及分析：
调试前，把一些语法等错误清楚后，发现没有输出运行结果。
之后进行调试。
调试时发现如下问题：
1、栈空的函数返回值与调用时的值运用错误。
导致在knap sack函数中的循环循环一次就退出来了。
因此，这种错误值得注意。
2、接着，发现第一个循环while 不能先判断条件，而只需先做再判断条件。
之后就改为do,,while 循环。
3、调试时，发现对栈中的元素个数不能清楚地看到，因此在栈的结构体中加入了一个num 域。
这样，调试时对栈就能清楚的了解其中入站和出站的过程。
4、后来发现运行只出现了三组结果。
继续考察，调试，其中，输出三组结果后，循环跳出来了。
原来栈中的元素已经为空，即在新的元素入栈前，栈已为空，于是，将
Pop( S, pk)//退出栈顶物品
T+=w[k];
k++;//继续考察下一件物品
提到循环最前面，并加上判断的if。
这样才输出了正确结果。
5、最后，把程序中的一些小环节加以注释，还有把没有匹配的要提示。
从而使程序更好的使用，使其更健壮，更完善。
