2638: 分支限界法-0-1背包问题

#include <stdio.h>

// 为了方便编写限界函数，假设按照单位重量获利递增的顺序输入每个物品的重量和获利。
#define MaxSize 100	//最多节点数

int n; //物品数量
int c; //背包容量

int w[MaxSize];	//依次存放各个物品的重量，0号单元不用 
int v[MaxSize];	//依次存放各个物品的价值，0号单元不用
int bestx[MaxSize];	//存放程序执行过程中已经找到的当前最优解，0号单元不用
int bestv=0; //存放程序执行过程中已经找到的当前最优值

typedef struct {
	int cw; // 当前已放物品的重量
	int cv; // 当前已放物品的获利
	int i; //当前在解空间树中的层数，假设根结点是第1层
	int x[MaxSize]; // 当前解向量
} QNode; //存放解空间树中的节点数据

typedef struct { //存放节点的顺序循环队列
	QNode Q[MaxSize];
	int front,rear;
} SqQueue;

void InitQueue(SqQueue &sq) { //队列初始化
	sq.front=0;
	sq.rear=0;
}

int QueueEmpty(SqQueue sq) { //判断队列是否为空
	if(sq.front==sq.rear) {
		return 1;
	} else {
		return 0;
	}
}

int QueueFull(SqQueue sq) { //判断队列是否为满
	if(sq.front==(sq.rear+1)%MaxSize) {
		return 1;
	} else {
		return 0;
	}
}

void EnQueue(SqQueue &sq, QNode e) { //入队
	if(!QueueFull(sq)) {
		sq.Q[sq.rear]=e;
		sq.rear=(sq.rear+1)%MaxSize;
	} else {
		printf("Error:queue is full\n");
	}
}

void DeQueue(SqQueue &sq, QNode &e) { //出队
	if(!QueueEmpty(sq)) {
		e=sq.Q[sq.front];
		sq.front=(sq.front+1)%MaxSize;
	} else {
		printf("Error:queue is empty\n");
	}
}

void BB() {
	SqQueue sq;
	InitQueue(sq);
	// 构造根结点
	QNode e;
	e.cw=0;
	e.cv=0;
	e.i=1;
	EnQueue(sq,e);
	while(!QueueEmpty(sq)) {
		DeQueue(sq,e);
		if(e.i==n+1) {// 处理解空间树中的叶子结点
			if(e.cv>=bestv){
				bestv=e.cv;
				for(int j=1; j<=n; j++) {
					bestx[j]=e.x[j];
				}
			}	
		} else { // 处理解空间树中的非叶子结点
			//处理左孩子，要该物品
			QNode le=e;
			___________ 
			le.i++; // 准备好进入下一层
			if(le.cw<=c) { // 如果满足约束条件
				EnQueue(sq,le);
			}
			//处理右孩子，不要该物品
			QNode re=e;
			_____________
			re.i++;  // 准备好进入下一层
			EnQueue(sq,re);
		}
	}
}

int main(void) {
	scanf("%d %d",&n,&c);
	for(int i=1; i<=n; i++) {
		scanf("%d",&w[i]);
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&v[i]);
	}
	BB();
	printf("%d\n",bestv);
	return 0;
}

3 50
45 25 25
28 15 15

30