分支限界.txt

用分支限界法求解背包问题（0/1背包） 1.问题描述：已知有N个物品和一个可以容纳TOT重量的背包

用分支限界法求解背包问题（0/1背包）

1.问题描述：已知有N个物品和一个可以容纳TOT重量的背包，每种物品I的重量为Weight，价值为Value。一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总价值最大。

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示装入，右表示不装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

代码如下：

//res.cpp

#include <iostream.h>

struct good
{
	int weight;//物品重量
	int value;//物品价值
	int flag;//是否装入标记
};

int number;//物品数量
int TOT;//背包最大可承载重量
int upbound=0;//背包上界
int curv=0, curw=0;//当前价值与重量
good *bag=NULL;

void Init_good()//构建物品结点
{
	bag=new good [number];
	for(int i=0; i<number; i++)
	{
		cout<<"第"<<i+1<<"件物品重量(Weight):";
		cin>>bag[i].weight;
		cout<<"第"<<i+1<<"件物品价值(Value):";
		cin>>bag[i].value;
		bag[i].flag=0;//初始标志，为"0"时不装入背包
		cout<<endl;
	}
}

int getbound(int m, int *bound_u)//返回当前结点的价值上限
//m、*bound_u 分别表示当前背包内的物品数量和价值
{
	for(int w=curw, v=curv; m<number && (w+bag[m].weight)<=TOT; m++)
	{
		w=w+bag[m].weight;
		v=w+bag[m].value;
	}
	*bound_u=v+bag[m].value;
	return (v+bag[m].value*((TOT-w)/bag[m].weight));
}

void LCbag()//遍历结点并选择装入的结点
{
	int bound_u=0, bound_c=0;//当前结点的u限界和c限界
	for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品
	{
		if((bound_c=getbound(i+1, &bound_u))>upbound )//遍历左子树
			upbound=bound_u;//更改已有u限界,不更改标志  
		if( getbound(i, &bound_u)>bound_c )//遍历右子树
  //若装入，判断左子树的c限界是否大于右子树根的c限界，是则装入
		{
			upbound=bound_u;//更改已有u限界
			curv=curv+bag[i].value;
			curw=curw+bag[i].weight;//从已有重量和效益加上新物品
			bag[i].flag=1;//标记为装入
		}
	}
}

void Display()//显示
{
	cout<<"可放入背包的物品编号为:";
	for(int i=0; i<number; i++)
		if(bag[i].flag>0)cout<<i+1<<" ";
	cout<<endl;
	delete []bag;
}

void main()
{
	cout<<"分支限界法解背包问题"<<endl<<endl;
	cout<<"请输入物品数量(N):";
	cin>>number;
	cout<<"请输入背包最大可承载重量(TOT):";
	cin>>TOT;
	cout<<endl;
	Init_good();
	LCbag();
	cout<<"运行结果:"<<endl<<endl;
	cout<<"背包内最大价值为:"<<curv<<endl;
	Display();