求解0/1背包箱问题。分别用先进先出队列分支限界法和优先队列分支限界法实现。
时间: 2024-05-03 17:17:26 浏览: 104
0-1背包问题(分支限界法)
0/1背包问题是一种经典的组合优化问题,旨在找到一种最佳的方式来填充一个容量为W的背包,使得总价值最大。其中,每个物品有一定的价值和重量,背包有一定的容量限制,每个物品要么放入背包中,要么不放入背包中。
先进先出队列分支限界法:
先进先出队列分支限界法的基本思想是维护一个先进先出队列Q,队列中存储当前搜索节点的信息。每次取出队首节点扩展,扩展得到的子节点按照价值的非增序列插入到队尾。当节点的上界小于当前最优解时,放弃搜索。
步骤如下:
1.将节点信息插入到队列Q中。
2.从队列Q中取出队首节点。
3.若该节点是一个叶节点,则更新当前最优解。
4.否则,计算该节点的上界。若上界小于当前最优解,则放弃搜索。
5.按照价值的非增序列,扩展该节点子节点,并将子节点信息插入到队列Q的队尾。
6.重复2-5步骤,直到队列Q为空。
优先队列分支限界法:
优先队列分支限界法的基本思想是维护一个优先队列Q,队列中存储当前搜索节点的信息。每次取出优先级最高的节点扩展,扩展得到的子节点按照价值的非增序列插入到优先队列Q。当节点的上界小于当前最优解时,放弃搜索。
步骤如下:
1.将节点信息插入到优先队列Q中。
2.从优先队列Q中取出优先级最高的节点。
3.若该节点是一个叶节点,则更新当前最优解。
4.否则,计算该节点的上界。若上界小于当前最优解,则放弃搜索。
5.按照价值的非增序列,扩展该节点子节点,并将子节点信息插入到优先队列Q中。
6.重复2-5步骤,直到优先队列Q为空。
参考代码如下(Python实现):
先进先出队列分支限界法:
```python
from queue import Queue
class Node:
def __init__(self, value, weight, level):
self.value = value
self.weight = weight
self.level = level
def __lt__(self, other):
return self.value > other.value # 按照价值的非增序列排序
def bound(node, n, W):
if node.weight >= W:
return 0
value = node.value
j = node.level + 1
total_weight = node.weight
while j < n and total_weight + weights[j] <= W:
total_weight += weights[j]
value += values[j]
j += 1
if j < n:
value += (W - total_weight) * values[j] / weights[j]
return value
def knapsack_bfs(n, W, values, weights):
q = Queue()
root = Node(0, 0, -1)
max_value = 0
q.put(root)
while not q.empty():
node = q.get()
if node.level == n - 1:
if node.value > max_value:
max_value = node.value
else:
if bound(node, n, W) > max_value:
left = Node(node.value + values[node.level + 1], node.weight + weights[node.level + 1], node.level + 1)
right = Node(node.value, node.weight, node.level + 1)
q.put(left)
q.put(right)
return max_value
```
优先队列分支限界法:
```python
from queue import PriorityQueue
class Node:
def __init__(self, value, weight, level):
self.value = value
self.weight = weight
self.level = level
def __lt__(self, other):
return self.value > other.value # 按照价值的非增序列排序
def bound(node, n, W):
if node.weight >= W:
return 0
value = node.value
j = node.level + 1
total_weight = node.weight
while j < n and total_weight + weights[j] <= W:
total_weight += weights[j]
value += values[j]
j += 1
if j < n:
value += (W - total_weight) * values[j] / weights[j]
return value
def knapsack_pq(n, W, values, weights):
pq = PriorityQueue()
root = Node(0, 0, -1)
max_value = 0
pq.put(root)
while not pq.empty():
node = pq.get()
if node.level == n - 1:
if node.value > max_value:
max_value = node.value
else:
if bound(node, n, W) > max_value:
left = Node(node.value + values[node.level + 1], node.weight + weights[node.level + 1], node.level + 1)
right = Node(node.value, node.weight, node.level + 1)
pq.put(left)
pq.put(right)
return max_value
```
测试代码:
```python
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
n = len(values)
print(knapsack_bfs(n, W, values, weights)) # 输出220
print(knapsack_pq(n, W, values, weights)) # 输出220
```
阅读全文