r_back01.c

回溯法求01背包问题,c语言版本

#include <stdio.h>
#include <string.h>
#define LEN 1000
/**********************************************/
/*　　　存放物品重量wight[]，价值value[]　　　*/
/*      存放物品编号number[]    　　 　　　　 */
/*  　　存放当前选中的物品编号way[]   　　　　*/
/*　　　存放最大价值时选择的物品编号be[]　　　*/
/*   　 物品数N，背包容量M           　　　　 */
/* 　　 背包当前重量cw，背包当前价值cv      　*/
/* 　　 当前最优价值bestv,最终最优值LV      　*/
/**********************************************/
int wight[LEN],value[LEN],number[LEN];
int way[LEN],be[LEN];
int N,M;
double cw,cv,bestv,LV; 
/***********************************************/
/*  　　　选择排序,按单位价值从大到小  　　 　 */
/***********************************************/
void selectsort(){
	int i,j,k,temp;
	double temp1,temp2;
	for(i=0;i<N;i++){
		k=i;
		temp1=1.0*value[i]/wight[i];
		for(j=i+1;j<N;j++){
			temp2=1.0*value[j]/wight[j];   
			if(temp1<temp2){
				k=j;temp1=temp2;     
			}
		}
		temp=value[i];
		value[i]=value[k];
		value[k]=temp;
		temp=wight[i];
		wight[i]=wight[k];
		wight[k]=temp;
		temp=number[i];
		number[i]=number[k];
		number[k]=temp; 
	} 
}

/************************************************/
/*      　　　　计算上界函数bound      　　　   */
/*     　　　　 参数:i(int)第i个物品   　　　   */
/*     　　　　 syw(int)背包剩余容量   　　　   */
/*     　　　　 bv(int)不可能达到的上界   　　　*/
/************************************************/
double bound(int i){
	double syw,bv;
	syw=M-cw;bv=cv;
	while(i<=N && wight[i]<=syw){
		syw-=wight[i];
		bv+=value[i];
		i++;
	}

	if(i<=N){
		//1.0出现的目的是将其它数转化为double型；
		bv+=syw*1.0*value[i]/wight[i];  
	} 
	return bv;
}

/**********************************************/
/* 　　　 回溯搜索解空间函数backtrack   　　　*/
/*  　　　参数:ii(int)当前处理的物品  　　　  */
/**********************************************/
void backtrack(int ii){
	int k;
	/*当到达叶子节点时,返回当前价值*/
	if(ii>=N){
		bestv=cv;
		if(bestv>LV){
			for(k=0;k<N;k++){
				be[k]=way[k];     
			}
		LV=bestv;
		} 
		return;
	 }
	 /*回溯处理*/
	if(cw+wight[ii]<=M){
		cw+=wight[ii];
		cv+=value[ii];
		way[number[ii]]=1;
		backtrack(ii+1);
		cw-=wight[ii];
		cv-=value[ii];
		way[number[ii]]=0; 
	} 
	/*剪枝*/
	if(bound(ii+1)>bestv)
		backtrack(ii+1); 
} 

int main(){
	int  i;
	printf("*****************************************************************************");
	printf("\n");
	printf("                          以回溯法求解0/1背包问题                                     \n");
	printf("                        若输入的物品数量为0程序结束                                     \n");
	printf("*****************************************************************************");
	printf("\n");
	printf("请输输入物品的数量：");
	while(scanf("%d",&N) && N){
		/*初始化各参数*/
		memset(wight,0,sizeof(wight));
		memset(value,0,sizeof(value));
		memset(number,0,sizeof(number));
		memset(way,0,sizeof(way));
		memset(be,0,sizeof(be));
		M=0;cw=cv=0;
		bestv=LV=0;
		printf("请输入背包的容量：");
		scanf("%d",&M);
		/*输入每个物品的重量,价值*/
		for(i=0;i<N;i++){
			printf("请输入物品的重量和效益（以,分开）：");
			scanf("%d,%d",&wight[i],&value[i]);
			number[i]=i;
		}
		/*回溯*/
		backtrack(0);
		/*输出*/
		printf("结果：%.0lf:\t",LV);
		for(i=0;i<N;i++){
			printf("%d ",be[i]);
		}
		printf("\n请输入物品的数量：");
	}
	return 0;
}