01背包回溯法

计算机算法基础（第三版）（余祥宣、崔国华、等）华中科技大学出版社  中回溯法解决01背包问题：

算法思想：

基于贪心算法的回溯算法：

W、P数组是按照效益P/W拍好序的数组

#include <stdio.h>

const int N=8;//物品个数
const int M=110;
int W[N+1]={0,1,11,21,23,33,43,45,55};//重量数组,从1开始
int P[N+1]={0,11,21,31,33,43,53,55,65};//效益数组

//最终的重量和收益
int fw=0;
int fp=-1;
int X[N+1]={0};//记录最终物品的状态

//当前重量和收益
int cw=0;
int cp=0;

int Y[N+1]={0};//当前物品的状态


//限界函数
//p:当前效益，w：当前背包重，k：上次去掉的物品
//返回新收益
int bound(int p,int w,int k){
	for(int i=k+1;i<=N;i++){
		w+=W[i];
		if(w<M)p+=P[i];
		else return p+(1-(w-M)/W[i])*P[i];
	}
	return p;
}
void bag0_1(){
	int k=1;
	
	while(true){
		while(k<=N && cw+W[k]<=M){
			cw+=W[k];
			cp+=P[k];
			Y[k]=1;
			k++;
		}

		if(k>N){
			fp=cp;
			fw=cw;
			k=N;
			for(int i=0;i<=N;i++)X[i]=Y[i];
		}
		else Y[k]=0;

		while(bound(cp,cw,k)<=fp){
			while(k!=0&&Y[k]!=1)
				k--;

			if(k==0)return;

			Y[k]=0;
			cw-=W[k];
			cp-=P[k];
		}
		k++;
	}
}

int bound2(int p,int w,int k,int &pp,int &ww,int &i){
	pp=p;
	ww=w;
	for(i=k+1;i<=N;i++){
		if(ww+W[i]<=M){
			ww+=W[i];
			pp+=P[i];
			Y[i]=1;
		}
		else return pp+(M-ww)*P[i]/W[i];
	}
	return pp;
}

void bag0_1_2(){
	int k=0,pp,ww,j;
	while(true){
		while(bound2(cp,cw,k,pp,ww,j)<=fp){
			while(k!=0&&Y[k]!=1)
				k--;
			if(k==0)return;

			Y[k]=0;
			cw-=W[k];
			cp-=P[k];
		}
		cp=pp;
		cw=ww;
		k=j;

		if(k>N){
			fp=cp;
			fw=cw;
			k=N;
			for(int i=0;i<=N;i++)X[i]=Y[i];
		}
		else Y[k]=0;
	}
}
int main(){
	bag0_1_2();

	printf("收益%d\n",fp);
	printf("重量%d\n",fw);

	for(int i=1;i<=N;i++)printf("%d ",X[i]);
    return 0;
}

01背包回溯法,布布扣,bubuko.com

01背包回溯法

原文：http://blog.csdn.net/starcuan/article/details/20410573