2629: 回溯法-01背包问题

#include <stdio.h>
// 为了方便编写限界函数，假设按照单位重量获利递减输入每个物品的重量和获利。

int w[21]; //存储物品重量，0号单元不存储有效数据
int v[21]; //存储物品价值，0号单元不存储有效数据
int n;//存储物品个数
int c;//存储背包容量
int bestx[21]; //最优解，0号单元不存储有效数据
int x[21]; //当前解，0号单元不存储有效数据
int bestv;//最优值
int cv;//当前已经放到背包中的物品价值
int cw;//当前已经放到背包中的物品重量

double bound(int i) { //计算剩余物品(i:n)的上界
	int cleft=c-cw;  // 剩余容量
	int b=0;   // b是一个临时变量
	while(i<=n && w[i]<=cleft) {
		cleft-=w[i];
		b+=v[i];
		i++;
	}
	if (i<=n) {
		b+=1.0*v[i]/w[i]*cleft;  // 装满背包
	}
	return b;
}

void backtrack(int i) { // 搜索第i层结点

	if(i>n) { //到达叶结点考虑结束本次递归
		
	} else {
		if(cw+w[i]<=c) {  //搜索左子树，此时必须满足约束函数
			
		}
		if (cv+bound(i+1)>bestv) { //搜索右子树，使用限界函数的目的是为了剪枝，提高算法效率；此处也可以不考虑限界函数。 
			
		}
	}
}

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]);
	}
	cw=0;
	cv=0;
	backtrack(1);
	printf("%d\n",bestv);
	for(int i=1; i<=n; i++) {
		printf("%d ",bestx[i]);
	}
	return 0;
}

3 10
3 4 5
4 5 6

11
0 1 1