栈的练习——简单的背包问题

程序员文章站 2022-06-03 15:50:02

...

C栈的练习——简单的背包问题

-周硕 2018年3月28日

作业题3：假设有n件质量分配为w1，w2，…，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量“恰好”等于背包所能装载的最大质量，即wi1+wi2+…+wik=T。若能，则背包问题有解，输出所有解；否则输出无解。

思路：这道题用来熟悉栈的基本操作，其中包含了栈的操作——初始化(InitStack)、置入元素(Push)、弹出元素(Pop)。从3月26号晚上一直到3月28号上午的程序设计课，我一直在修改找出问题，今天上午终于大功告成。背包问题有更简单的算法，这里只是用来熟悉C的语法和做栈的练习。

首先定义栈的函数——InitStack、Push、Pop：（CSDN贴C代码没有高亮真的难受..）

//背包问题(栈)
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//OK表示操作成功，ERROR表示操作出错，OVERFLOW表示申请空间或插入时溢出
//STACK_INIT_SIZE表示栈的初始空间，当栈的空间不够用时每次再申请STACKINCREMENT的空间

typedef struct {
	int *base;
	int *top;
	int stacksize;
}SqStack;
//定义栈结构。base为栈底指针，top为栈顶指针，stacksize为栈的空间。

这里为了便捷，直接将base和top的指针类型设置成int类型，实际上还可以：

#define ElemType int 
typedef struct{
	ElemType * top;
	ElemType * base;
	int stacksize;
}SqStack;

函数声明：

 int InitStack(SqStack *S);
 int Push(SqStack *S,int e);//压入元素e 
 int Pop(SqStack *S);
 void Package(SqStack *S,float MaxWeight,int n,float weight[STACK_INIT_SIZE])
 //MaxWeight为最大质量，n为物品个数，数组weight用于储存各物品的重量

下面是栈的三个操作

int InitStack(SqStack *S)
{
	S->base=(int*)malloc(STACK_INIT_SIZE * sizeof(int));
	if(S->base==NULL) exit(OVERFLOW);
	S->top=S->base;
	return OK;
 } 
 
 int Push(SqStack *S,int e)
 {
 	if(S->top-S->base>=S->stacksize)
	 {
 		S->base=(int*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT) * sizeof(int));
		if(S->base==NULL) exit(OVERFLOW);
		S->top=S->base+STACK_INIT_SIZE; 
	 }
		*(S->top)=e;
	 S->top++;
	 return OK;
 }
 
 int Pop(SqStack *S)
 {
 	if(S->top==S->base) return ERROR;
 	S->top--;
 	return OK;
 }

这里需要注意的是栈顶指针和栈底指针的关系。当栈中没有元素时，S->top==S->base；当有元素被压入栈底时，top++，top指向栈顶元素的上一个空间。

在为栈申请空间或进行其他操作时，要尽可能考虑所有操作失败的情况，用ERROR或OVERFLOW进行返回。

main函数中进行输入和储存数据：

main()
 {
 	int n,i;//n为物品个数 
 	float MaxWeight;
 	SqStack S;
 	float data=0;
 	float weight[STACK_INIT_SIZE]; 
 	
	InitStack(&S);
 	printf("请输入背包容纳量：\n");
 	scanf("%f",&MaxWeight);
 	printf("请输入物品的个数：\n");
 	scanf("%d",&n);
 	printf("请分别输入物品质量:\n");
 
	for(i=0;i<n;i++){
		scanf("%f",&data);
		weight[i]=data;
	}
	/*printf("%f\n",MaxWeight);
	printf("%d\n",n);*/
	/*for(i=0;i<n;i++){
		printf("%f ",weight[i]);
	}*/
	printf("\n");
	Package(&S,MaxWeight,n,weight);
	return 0;
 	
 }

由于对C的语言规则还是不熟悉，main函数调试了好久，在scanf语句这里出现了问题：

float data;
/*scanf("%lf",&data);//Wrong*/
//这样数据无法储存进去，但是用%lf占位符可以输出
scanf("%f",&data);//Right
 printf("%lf",data);//Right

scanf的占位符卡的很严格，要注意这里！

Package函数：

void Package(SqStack *S,float MaxWeight,int n,float weight[STACK_INIT_SIZE])
{
	float CurrentWeight=0;
	int i=0;
	int flag=0;//flag用来判定是否有解。flag==0无解；flag==1有解。
	int* Ptr; 
	while(S->base!=S->top||i<n)
	{
		if(/*i<n&&*/CurrentWeight+weight[i]<=MaxWeight)
		{
			Push(S,i);
			CurrentWeight+=weight[i];//背包重量的变化不要忽略 
			//printf("@@");
		}
		
		if(CurrentWeight==MaxWeight)
		{
			Ptr=S->base;
			flag=1;
			while(Ptr!=S->top)
			{
				printf("%f ",weight[*(Ptr)]);
				Ptr++;
			}//end for while
			printf("\n");
			Pop(S);
			CurrentWeight-=weight[i];
			if(i==n-1)
			{
				if(S->top==S->base)
				{
					i++;
				}
				else
				{
					i=*(S->top-1);
					i++;
					CurrentWeight-=weight[*(S->top-1)];
					Pop(S);
				}
			}
			else
			{
				i++;
			 } 
		}//end for if
		
		else /*CurrentWeight<MaxWeight*/
		{
			if(i<n-1) i++;
			else//走到了最后一个元素 
			{
				if(*(S->top-1)!=n-1)//最后一个元素没有放入栈底
				{
					i=*(S->top-1);
					i++;
					CurrentWeight-=weight[*(S->top-1)];
					Pop(S);
					//printf("//");
				} 
				else//最后一个元素放入栈底 
				{
					CurrentWeight-=weight[n-1];
					Pop(S);
					if(S->base==S->top) 
					{
					i++;
					//printf("$$");
					}
					//如果栈内没有元素了，使i=n结束循环 
					else//否则再pop一个元素 
					{
						i=*(S->top-1);
						i++;
						CurrentWeight-=weight[*(S->top-1)];
						Pop(S);
						//printf("^^");	
					}
				}
			}//end for else 
		}//end for else CurrentWeight<MaxWeight
	}//end for while
	if(flag==0) printf("没有合适的装法\n");
 } //end for Package

整个Package子函数的思路大概是这样：

栈的练习——简单的背包问题