【分支限界法】求解0/1背包问题_o-1背包分支限界c语言

问题描述

0/1背包问题。假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25,
12)，背包容量W=10，计算背包所装入物品的最大价值。

求解思路

首先，将给定物品按单位重量价值从大到小排序，结果如下：

  应用贪心法求得近似解为(1, 0, 1, 0)，获得的价值为65，这可以作为0/1背包问题的下界。
  如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目标函数的界[65, 100]。
  限界函数为：

目标函数的界[65, 100]

  分支限界法求解0/1背包问题，其搜索空间如图所示，具体的搜索过程如下：
（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100；
（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40 + (10-4)×6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入表PT中；

（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；
（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40 + (10-4)×5=70，将结点5加入表PT中；

（5）在表PT中选取目标函数值取得极大的结点5优先进行搜索；
（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65 + (10-9)×4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40 + (10-4)×4＝64，将结点6加入表PT中；

（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索；
（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；
（9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。

假设求解最大化问题，解向量为X=(x1, x2, …, xn)，其中，xi的取值范围为某个有穷集合Si，|Si|=ri（1≤i≤n）。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界[down, up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能取得的目标函数值bound(x1)，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于bound(x1)，也就是部分解应满足：
bound(x1)≥bound(x1, x2)≥ … ≥bound(x1, x2, …, xk)≥ … ≥bound(x1, x2, …, xn)
若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。从表PT中选取使目标函数取得极大值的结点作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行解X=(x1, x2, …, xn)及其目标函数值bound(x1, x2, …, xn)。
如果bound(x1, x2, …, xn)是表PT中目标函数值最大的结点，则bound(x1, x2, …, xn)就是所求问题的最大值，(x1, x2, …, xn)就是问题的最优解；
如果bound(x1, x2, …, xn)不是表PT中目标函数值最大的结点，说明还存在某个部分解对应的结点，其上界大于bound(x1, x2, …, xn)。于是，用bound(x1, x2, …, xn)调整目标函数的下界，即令down=bound(x1, x2, …, xn)，并将表PT中超出目标函数下界down的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表PT中最大。

代码实现

}*/
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//物品个数
int n;
//背包容量
int c;
//定义物品结构体
struct Item
{
   
	//物品编号
	int ItemID;
	//物品价值
	int value;
	//物品重量
	int weight;
	//质量/重量
	int ratio;
};

//定义搜索节点
struct Node
{
   
	Node(){
   
		value = 0;
		weight = 0;
		level = 0;
		parent = 0;
		bound = 0;
	}
	//搜索到该节点的价值
	int value
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
31
32
33
34
35
36