回溯法解决01背包问题_采用回溯法解决0-1背包问题

目录

一、分析

（一）定义问题的解空间

（二）确定解空间的组织结构

（三）搜索解空间

 1. 约束条件

2. 限界条件

（四）搜索过程

二、举例

三、核心代码

四、完整代码

---

一、分析

（一）定义问题的解空间

• 问题的解是从n个物品中选择一些物品使其在不超过容量的情况下价值最大。每个物品有且只有两种状态，要么装入背包，要不不装入。那么第i个物品装入背包，能够达到目标要求，还是不装入背包能够达到目标要求呢?很显然，目前还不确定。因此，可以用变量xi表示第i种物品是否被装入背包的行为，如果用“0”表示不被装入背包，用“1”表示装入背包，则xi的取值为0或1。 
• 问题的解空间是{x1,x2,....x1,...xn}，显约束是xi=0或1

（二）确定解空间的组织结构

问题的解空间描述了2ⁿ 种可能解，也可以说是n个元素组成的集合所有子集个数。例如3个物品的背包问题,解空间是:{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}。该问题有2³个可能解。可见，问题的解空间树为子集树，解空间树的深度为问题的规模n 

（三）搜索解空间

1. 约束条件

解空间包含2ⁿ种可能解，存在某种或某些物品无法装入的情况，因此需要设置约束条件，判断装入背包的物品总重量是否超出背包容量，如果超出，为不可行解；否则为可行解。搜索过程不再搜索那些导致不可行解的结点及其孩子结点。

2. 限界条件

• 背包问题的可行解可能不止一个，问题的目标是找一个装入背包的物品总价值最大的可行解，即最优解。因此，需要设置限界条件来加速找出该最优解的速度。根据解空间的组织结构，对于任何一个中间结点z(中间状态)，从根结点到z结点的分支所代表的状态(是否装入购物车)已经确定，从z到其子孙结点的分支的状态是不确定的。
• 也就是说，如果z在解空间树中所处的层次是t，说明第1种物品到第t-1种物品的状态已经确定了。我们只需要沿着z的分支扩展很容易确定第t种物品的状态。那么前t种物品的状态就确定了。但第t+1种物品到第n种物品的状态还不确定。这样，前t种物品的状态确定后，当前已装入背包的物品的总价值，用cp表示。已装入物品的价值高不一定就是最优的，因此还有剩余物品未确定。
• 我们还不确定第t+1种物品到第n种物品的实际状态，因此只能用估计值。假设第t+1种物品到第n种物品都装入背包，第t+1种物品到第n种物品的总价值用rp来表示，因此cp+rp是所有从根出发经过中间结点z的可行解的价值上界

（四）搜索过程

• 从根结点开始，以深度优先的方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。由于子集树中约定左分支上的值为“1”，因此沿着扩展结点的左分支扩展，则代表装入物品。
• 此时，需要判断是否能够装入该物品，即判断约束条件成立与否，如果成立，即生成左孩子结点，左孩子结点成为活结点，并且成为当前的扩展结点，继续向纵深结点扩展；如果不成立，则剪掉扩展结点的左分支，沿着其右分支扩展，右分支代表物品不装入购物车，肯定有可能导致可行解。
• 但是沿着右分支扩展有没有可能得到最优解呢?这一点需要由限界条件来判断。如果限界条件满足，说明有可能导致最优解，即生成右孩子结点，右孩子结点成为活结点，并成为当前的扩展结点，继续向纵深结点扩展；如果不满足限界条件，则剪掉扩展结点的右分支，向最近的祖宗活结点回溯。搜索过程直到所有活结点变成死结点结束。 

二、举例

 

 

三、核心代码

double Bound(struct goods* ps, int i)//计算上界（即当前价值和剩余物品总价值）
{
	double sum = 0.0;//用于保存剩余物品价值
	while (i < n)
	{
		sum += ps[i].v;
		i++;
	}
	return sum+cv;
}

void Backtrack(struct goods* ps, int i)//回溯
{
 
	if (i >n-1)//已经到达了叶子结点（结束条件）
	{
		for (int k = 0; k < n; k++)
		{
			bestx[k] = ps[k].x;
		}
		bestv = cv;
		return;
	}
 
	if (cw + ps[i].w <= bagW)//满足条件,扩展左分支
	{
		ps[i].x = true;//当前物品放入背包
		cw += ps[i].w;//更新当前背包总重量
		cv += ps[i].v;//更新当前背包总价值
		Backtrack(ps, i + 1);
 
		ps[i].x = false;//回溯
		cw -= ps[i].w;//更新当前背包总重量
		cv -= ps[i].v;//更新当前背包总价值
	}
 
	if (Bound(ps, i + 1) > bestv)//满足条件，扩展右分支
	{
		ps[i].x = false;
		Backtrack(ps, i + 1);
	}
}

四、完整代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MAX 20//物品最多数量
struct goods
{
	double w;//物品重量
	double v;//物品价值
	bool x;//物品是否放入背包
}g[MAX];
 
 
int n , bagW ;//物品数量和背包容量
double cw ;//当前放入背包的重量
double cv ;//当前放入背包的总价值
double bestv ;//当前最优价值
bool bestx[MAX];//当前最优解集合
 
//初始化物品信息
void Init( struct goods* ps, int n);
//限界函数
double Bound(struct goods* ps, int i);
//回溯
void Backtrack(struct goods* ps, int i);
//
void Knapsack(struct goods* ps, int _bagW);
 
void Init(struct goods* ps,int n)//初始化物品信息
{
	cout << "请依次输入物品的重量和价值：\n";
	for (int i = 0; i < n; i++)
	{
		cin >> ps[i].w >> ps[i].v;
		ps[i].x = false;
	}
}
 
double Bound(struct goods* ps, int i)//计算上界（即当前价值和剩余物品总价值）
{
	double sum = 0.0;//用于保存剩余物品价值
	while (i < n)
	{
		sum += ps[i].v;
		i++;
	}
	return sum+cv;
}
 
void Backtrack(struct goods* ps, int i)//回溯
{
 
	if (i >n-1)//已经到达了叶子结点（结束条件）
	{
		for (int k = 0; k < n; k++)
		{
			bestx[k] = ps[k].x;
		}
		bestv = cv;
		return;
	}
 
	if (cw + ps[i].w <= bagW)//满足条件,扩展左分支
	{
		ps[i].x = true;//当前物品放入背包
		cw += ps[i].w;//更新当前背包总重量
		cv += ps[i].v;//更新当前背包总价值
		Backtrack(ps, i + 1);
 
		ps[i].x = false;//回溯
		cw -= ps[i].w;//更新当前背包总重量
		cv -= ps[i].v;//更新当前背包总价值
	}
 
	if (Bound(ps, i + 1) > bestv)//满足条件，扩展右分支
	{
		ps[i].x = false;
		Backtrack(ps, i + 1);
	}
}
 
void Knapsack(struct goods* ps,int _bagW)
{
	//初始化
	cw = 0.0;//当前放入背包的重量
	cv = 0.0;//当前放入背包的总价值
	bestv = 0.0;//当前最优价值
 
	double sw = 0.0;//保存所有物品总重量
	double sv = 0.0;//保存物品总价值
 
	for (int i = 0; i < n; i++)
	{
		sw += ps[i].w;
		sv += ps[i].v;
	}
 
	if (sw <= bagW)//意味着所有物品都可以装入
	{
		cout << "所有物品都可以放入购物车，且放入的总价值为：" << sv << endl;
		return;
	}
 
	Backtrack(ps, 0);
	cout << "放入背包的物品序号为：\n";
	for (int k = 0; k < n; k++)
	{
		if (bestx[k] == true)
			cout << k << " ";
	}
	cout << endl;
	cout << "放入的总价值为：" << bestv << endl;
}
int main()
{
	cout << "请分别输入物品的数量和背包总重量：\n";
	cin >> n >> bagW;
	Init(g, n);//初始化
	Knapsack(g, bagW);
	return 0;
}
 
 
//请分别输入物品的数量和背包总重量：
//4 10
//请依次输入物品的重量和价值：
//2 6
//5 3
//4 5
//2 4
//放入背包的物品序号为：
//0 2 3
//放入的总价值为：15