算法分析之0/1背包问题---回溯法实现

【问题描述】有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。 设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且满足重量限制（装入背包中物品重量和恰好为W ），并能具有最大的价值。 

【提示】该问题的解空间是一棵子集树！

    （1）对第i层上的某个分枝结点，对应的状态为dfs(i，tw，tv，op)，其中tw表示装入背包中的物品总重量，tv表示背包中物品总价值，op记录一个解向量。该状态的两种扩展如下图所示：

（2）左剪枝：对于第i层的有些结点，如果tw+w[i]已超过了W，显然再选择w[i]是不合适的；

（3）右剪枝：rw=w[i]+w[i+1]+…+w[n]， 当不选择物品i时：rw-w[i]=w[i+1]+…+w[n]，若tw+rw-w[i]

参考代码为：

void dfs(int i,int tw,int tv,int rw,int op[])

{  //初始调用时rw为所有物品重量和

   int j;

   if (i>n) //找到一个叶子结点

   {  if (tw==W && tv>maxv) //找到一个满足条件的更优解,保存

      {  maxv=tv;

         for (j=1;j<=n;j++) //复制最优解

            x[j]=op[j];

      }

   }

   else //尚未找完所有物品

   {  if (tw+w[i]<=W) //左孩子结点剪枝

      {  op[i]=1; //选取第i个物品

         dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op);

      }

      if (  tw+rw-w[i]>=W )

      {  op[i]=0;  //不选取第i个物品,回溯 

          dfs(i+1,tw,tv,rw-w[i],op);

      }

   }

}

【算法时间复杂度分析】

该算法不考虑剪枝时解空间树中有2n+1-1个结点（剪枝的结点个数不确定），所以最坏情况下算法的时间复杂度为O(2n)

【思考】如果要求：装入背包中物品重量和不超过W ，那么该如何剪枝？

源代码部分：

#include
using namespace std;
int n,W;
int maxv;//用于存放最优解对应的总价值 
void dfs(int w[],int v[],int x[],int i,int tw,int tv,int op[],int rw){
	if(i>n){  //找到一个叶子节点 
		if(tw==W && tv>maxv){
			maxv=tv;
			for(int j=1;j<=n;j++) x[j]=op[j];
		}
	}
	else{
		if(tw+w[i]<=W){
			op[i]=1;  //选取第i个物品 
			dfs(w,v,x,i+1,tw+w[i],tv+v[i],op,rw-w[i]);
		}
		if(tw+rw-w[i]>=W){  //直接减去w[i]是因为当前是讨论不选择该物品的情况 
			op[i]=0;  //不选第i个物品 则回溯 
			dfs(w,v,x,i+1,tw,tv,op,rw-w[i]);
		}
	}
} 
int main(){
	while(cin>>n>>W){  //输入物品的数量 
		int w[n+1],v[n+1];  //分别用来存储物品的重量和价值  默认都不使用0下标 
		int x[n+1];  //用于存放最终解
		maxv=0;int rw;//rw用于存储某个位置及其后续所有物品的价值总和 
		cout<<"please input the weight of n"<>w[i];rw+=w[i];}  //rw存储所有物品重量的总和 
		cout<<"please input the value of n"<>v[j];
		int tw=0,tv=0,op[n+1];
		dfs(w,v,x,1,tw,tv,op,rw);  //rw的初始值为所有物品的价值总和 
		cout<<"Result"< 
 运行结果部分：