【算法导论12】分支限界法—01背包问题_分支定界法求背包问题

12分支限界法—01背包问题

问题描述：
一个背包有固定体积和容量两个参数，针对n件商品，商品包含体积和价值两个参数，如何选择商品的装入，使得背包所装入的总价值最大。

问题分析：
一个商品有装和不装两种状态，因此此问题的解可以用一颗二叉树来表示，二叉树根节点到叶节点的路径穷举就是所有的选择。在此基础上，再删去不符合条件的结点路线即可。下面对此算法进行优化：
考虑三个问题：
1、如何确定某个结点选还是不选。
2、如何设计算法实现当某个结点已经不符合限制或最优解时，对结点进行剪枝。
3、如何设计算法实现从某一个结点的计算快速跳到另一个结点继续计算。

针对问题一：通过计算当前选择下背包的价值上限，将该结点加入优先队列，优先选择价值上限最大的结点（使用贪心算法，对剩余结点进行排序，不考虑不可分割，尽量多的选择单位价值最大的商品），来确定选择哪个分支。
针对问题二：设计左剪枝函数，如果当前结点选择时（该节点左分支），所选物品的总体积已经超过背包体积，则剪枝该结点。 此步骤需要获取每个结点下当前总体积。 设计右剪枝函数，当当前结点不选择时，此时价值上限<当前最大已选最大价值（随着结点的选择不断向上更新，数值变大），则对右分支进行剪枝。
针对问题三：使用优先队列，按照价值上限进行优先选择，实现从某个结点快速跳到其他结点的选择。

01背包分支限界法伪代码：

//伪代码
int MaxKnapsack(){
	while(非叶节点){//没有找到结果
		if(当前体积<=背包体积){//左分支剪枝函数
			if(当前价值>最大价值)//向上更新最大价值
				最大价值 = 当前价值；
			add(左节点)；//左节点加入优先队列	
		}
		bound()；//计算上限
		if（上限>最大价值）{//当不选择该结点时，后面全部按照最优选择计算，结果>最大价值时，才考虑。
			add（右节点）;//右节点加入优先队列
		}
		heapnode N；//堆排序
		H->deletemax(N);//从优先队列中取下一个活结点。
	}
}
//计算上限
int bound(int i){
	int left = 剩余容量；
	int b = 价值上限变量;
	while(i<=n && 第i个物品重量<=剩余容量){
		left -=第i个物品重量；
		b+=第i个物品价值；
		i++；
	}
	if(i<=n){//如果第i个物品重量>剩余容量，则选择“部分”该物品:贪心策略
		b+=第i个物品单位价值*剩余容量；
	}
	return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

20201202更新：
分支限界法思路分析：（以01背包为例子）
1 首先考虑暴力法，对所有情况进行穷举，由于每件物品有选和不选两种情况，所以解空间是二叉树
2 对所有穷举出的情况进行筛选：首先删除容量超过背包的情况，其次在剩下的情况中选择价值最大的情况。
3 对该过程进行优化：