回溯算法解决问题（C语言）

• 前言
• 一、实验步骤及结果
• 总结

解决问题：
通过回溯算法设计背包问题：
有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且具有最大的价值。
对下表所示的4个物品求出W=6时的所有解和最佳解。

#include
int weight[100];
int value[100];
int n,max_weight,max_value;
 
int best[100],tree[100];
void x(){
	printf("--------------------------------------------n");
}
 
void s()
{
	int i,j,k,l;
	x();
	printf("所能选的最大价值是%dn",max_value);
	printf("最佳选填方案为: ");
	for(i=1;i<=n;i++){
		if(best[i]==1)
			printf("t选择第%d个",i);
		    printf("n");
	}}
 
void foolish(int length,int allweight,int allvalue)
{
	if(length>=n+1)
	{
		if(allvalue>max_value)
		{
			int i;
			max_value = allvalue;
			for(i=1;i<=n;i++)
				best[i] = tree[i];
		}
	}
	else
	{
		if(allweight>=weight[length+1])
		{
			allweight = allweight - weight[length+1];
			allvalue = allvalue + value[length+1];
			tree[length+1] = 1;
			foolish(length+1,allweight,allvalue);
			tree[length+1] = 0;
			allweight = allweight + weight[length+1];
			allvalue = allvalue - value[length+1];
		}
		foolish(length+1,allweight,allvalue);
	}
}
 
void init()
{
	int i;
	max_value = 0;
	for(i=1;i<=n;i++)
		tree[i] = 0;
}
 
void main()
{
	int i,j,k,l;
	x();
	printf("请输入物品数量： ");
	scanf("%d",&n);
	printf("请输入背包容量： ");
	scanf("%d",&max_weight);
	x();
	{
		for(i=1;i<=n;i++)
			{printf("请输入第%d个物品质量： ",i);
		scanf("%d",&weight[i]);}
		x();
		for(j=1;j<=n;j++)
			{printf("请输入第%d个物品价值： ",j);
		scanf("%d",&value[j]);}
		init();
		foolish(0,max_weight,0);
		s();
		}
}

实验结果：

本次实验的难点在于如何剪枝，刚开始的我仅仅只使用了剪枝而没有回溯导致显示结果不正常，emmm回溯小难需要自己花心思学。