01背包问题 —— 【算法设计】分支限界法_01背包分支限界法

分支限界

问题背景

有N个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
注意：01背包问题要求一个物品只有0/1两种状态，即装入背包或不装入背包。不能将物品拆分成更小的单位装入，即不能部分装入。对于物品可以部分装入背包的问题，称之为背包问题

---

分支限界

• 基本思想
  分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
  在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
• 与回溯法的区别

1. 求解目标：
   回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
2. 搜索方式的不同：
   回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

---

分支限界下的01背包问题

• 思想
  采用优先队列方式，按照物品的单位价值从大到小进行优先级排序，使用大根堆结构存储物品数据。
  构造上界函数maxbound( )计算当前结点下的价值上界，如果当前结点下的价值上界比当前的最优值大，则将当前结点加入堆中，否则剪去该节点下的所有路径(即剪去子集树的枝)，直到堆中所有结点均被弹出。
• 过程

1. 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列
2. 节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和
3. 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中
4. 当右儿子结点满足上界约束时将它加入子集树和活结点优先队列

---

分支限界01背包-Python代码

本代码为python3下的分支限界01背包代码
关键步骤已标记注释

import heapq

# 物品信息
weight=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
value=[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]

print("物品信息如下：")
print("重量：")
print(weight)
print("价值：")
print(value)
# 背包容量
maxcap=35
print("最大背包容量为：%d\n"%maxcap)
n=len(weight)
# 当前重量与当前价值
cweight=0
cvalue=0
# 最优价值
bestv=0
bests=[]
num=0
heap=[]
heapq.heapify

# 上界函数：计算当前结点下的价值上界
def maxbound(i):
	global cweight
	global cvalue
	global n
	global weight
	global value
	global maxcap
	left = maxcap-cweight
	b=cvalue
	while i<n and weight[i]<=left:
		left-=weight[i]
		b+=value[i]
		i+=1
	if i<n:
		b+=(value[i]/weight[i])*left
	return b


# 分支限界算法求解01背包
i=0
upper=maxbound(i)
str=''

while(1):
	wt=cweight+weight[i]
	#print("wt:")
	#print(wt)
	if wt<=maxcap:
		if cvalue+value[i]>bestv:
			#print("i=%d"%i)
			bestv=cvalue+value[i]
			#print("bestv=%d"%bestv)
			
			# 存储当前最优值的最优路径
			bests=str+'1'
			bests=bests+'0'*(n-len(bests))
		# 入堆： 由于python只有小根堆，因此通过对上界值取倒，实现上界值大，优先级高                         
		if i+1<n:
			heapq.heappush(heap,[1/upper,cweight+weight[i],cvalue+value[i],i+1,str+'1'])

	upper=maxbound(i+1)
	if upper>=bestv:
		if i+1<n:
			heapq.heappush(heap,[1/upper,cweight,cvalue,i+1,str+'0'])

	if len(heap)==0:
		print("%d个物品的状态（1为被装入背包，0为未被装入背包）：%s"%(n,bests))
		print("最优价值为： %d"%bestv)
		break

	#print("heap:")
	#print(heap)
	node=heapq.heappop(heap)
	upper=1/node[0]
	cweight=node[1]
	cvalue=node[2]
	i=node[3]
	str=node[4]
	#print('node:')
	#print(node)

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

• 测试运行
  

---

参考文章

https://www.cnblogs.com/ttltry-air/archive/2012/08/02/2620763.html

---

---

分界线

---

---

**************************
Date：2020/1/19           
Category：算法设计
Author：Ver.
**************************

1
2
3
4
5
6