以回溯的思想求解0-1背包问题

以回溯法的思想求解0-1背包问题

目录

介绍

求解

---

介绍

• 0-1背包问题

[问题描述]给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

• 回溯法解题的基本思想

1. 按贪心法的思路，优先装入单位价值高的物品。
2. 当剩余容量装不下最后考虑的物品时，再用回溯法修改先前的装入方案，直到得到全局最优解为止。

---

求解

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
using namespace std;
struct object
{
	int p;	//物品的价值 
	int w;	//物品的重量 
}*ob;

int cp = 0 , bestp = 0;	//cp存放当前的价值，bestp存放最优价值 
int num;	//物品的数量
int c;		//背包的容量 
int* x, *bestx; 

//自定义大小关系 
bool cmp(object a, object b)
{
	return a.p/a.w > b.p/b.w;
}

//输出
void putout()
{
	cout<<"物品放入背包的状态为：";
	for(int i = 0; i < num; i++)
	{
		cout<<setw(5)<<x[i];
	}
	
	cout<<" 获得的价值为："<<cp<<endl;
}

//回溯法求0-1背包
void knap(int t)	//t表示递归深度 
{
	if(t >= num)	//到达叶子节点 
	{
		if(bestp < cp)
		{
			bestp = cp;
			for(int i = 0; i < num; i++)
			{
				bestx[i] = x[i];
			}
		}
		
		putout();
	}
	
	else
	{
		if(ob[t].w <= c)	//搜索左枝，约束条件 
		{
			x[t] = 1; cp += ob[t].p; c -= ob[t].w;	//改变状态 
			knap(t+1);	//继续向下深度搜索
			x[t] = 0; cp -= ob[t].p; c += ob[t].w;	//恢复原有状态 
		}
		x[t] = 0;		//搜索右枝，无需约束条件 
		knap(t+1);
	}
} 

int main()
{
	cout<<"请输入物品的数量：";
	cin>>num;
	
	ob = new object[num];
	cout<<"请输入每个物品的重量：";
	
	for(int i = 0; i < num; i++)
	{
		cin>>ob[i].w;
	}
	
	cout<<"请输入每个物品的价值：";
	for(int i = 0; i < num; i++)
	{
		cin>>ob[i].p;
	}
	
	cout<<"请输入背包的容量：";
	cin>>c;
	
	x = new int[num];	//存放当前解
	bestx = new int[num];	//存放最优解
	
	sort(ob,ob+num,cmp);	//将物品根据单位价值从高到低排列 
	
	knap(0);
	
	cout<<"最优价值："<<bestp<<"\t";
	for(int i = 0; i < num; i++)
	{
		if(bestx[i] == 1)
		{
			cout<<i+1<<" ";
		}
	}
	
	return 0;
}

据此形成的部分空间树，如下图所示，其中的w[i]与代码中的ob[i].w相对应

运行结果截图：

---

前面算法完全搜索解空间树策略： 用约束条件确定是否搜索其左子树； 对右子树没有任何判断，一定进入右子树搜索，十分耗时，下面在原有代码基础上加入剪枝函数(右子树有可能包含最优解时才进入右子树搜索，否则将右子树减去）以优化。

剪枝方法具体如下：

1. r:当前剩余物品价值总和；
2. cv:当前获得价值；
3. bestp:当前最优价值；
4. 当cv+r<=bestp时，可剪去右子树。

计算右子树上界方法:

将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。

代码如下：

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
using namespace std;
struct object
{
	int p;	//物品的价值 
	int w;	//物品的重量 
}*ob;

int cp = 0 , bestp = 0;	//cp存放当前的价值，bestp存放最优价值 
int num;	//物品的数量
int c;		//背包的容量 
int cw = 0;		//计算当前的重量 
int* x, *bestx; 

//自定义大小关系 
bool cmp(object a, object b)
{
	return a.p/a.w > b.p/b.w;
}

//输出
void putout()
{
	cout<<"物品放入背包的状态为：";
	for(int i = 0; i < num; i++)
	{
		cout<<setw(5)<<x[i];
	}
	
	cout<<" 获得的价值为："<<cp<<endl;
}

//计算以结点i处为根节点的上界(限界条件) 
int bound(int i)
{
	int left = c - cw;	//剩余容量 
	int temp = cp;	 //当前价值
	while(ob[i].w <= left && i <= num)
	{
		temp += ob[i].p;
		left -= ob[i].w;
		i++;	
	} 
	
	//装满背包
	if(i <= num)
	{
		temp += left*ob[i].p/ob[i].w;	
	} 
	
	return temp;
}

//回溯法求0-1背包
void knap(int t)	//t表示递归深度 
{
	if(t >= num)	//到达叶子节点 
	{
		if(bestp < cp)
		{
			bestp = cp;
			for(int i = 0; i < num; i++)
			{
				bestx[i] = x[i];
			}
		}
		
		putout();
	}
	
	else
	{
		if(ob[t].w <= c)	//搜索左枝，约束条件 
		{
			x[t] = 1; cp += ob[t].p; c -= ob[t].w;	//改变状态 
			knap(t+1);	//继续向下深度搜索
			x[t] = 0; cp -= ob[t].p; c += ob[t].w;	//恢复原有状态 
		}
		
		if(bound(t+1) > bestp)	//限界搜索右枝 
		{
			x[t] = 0;		
			knap(t+1);
		}		
	}
} 

int main()
{
	cout<<"请输入物品的数量：";
	cin>>num;
	
	ob = new object[num];
	cout<<"请输入每个物品的重量：";
	
	for(int i = 0; i < num; i++)
	{
		cin>>ob[i].w;
	}
	
	cout<<"请输入每个物品的价值：";
	for(int i = 0; i < num; i++)
	{
		cin>>ob[i].p;
	}
	
	cout<<"请输入背包的容量：";
	cin>>c;
	
	x = new int[num];	//存放当前解
	bestx = new int[num];	//存放最优解
	
	sort(ob,ob+num,cmp);	//将物品根据单位价值从高到低排列 
	
	knap(0);
	
	cout<<"最优价值："<<bestp<<"\t";
	for(int i = 0; i < num; i++)
	{
		if(bestx[i] == 1)
		{
			cout<<i+1<<" ";
		}
	}
	
	return 0;
}

由此形成的空间树为

运行结果：

至此问题得到了一种解答。

注：这是本人第一次写博客，如有不足之处敬请批评指教！