我已经花了一周的时间编写这个背包问题的分支限界代码,并查阅了许多相关文章和书籍。然而,当我运行我的代码时,得到的结果并不是我期望的那样。输入来自于文本文件,像这样:
12
4 1
1 1
3 2
2 3
第一行表示背包容量,随后每一行都是价值/重量对。使用这个文件得到的结果是“8”,而不是“10”(除非我错了,所有物品都无法装入背包)。以下是我的代码:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import Queue
from collections import namedtuple
Item = namedtuple("Item", ['index', 'value', 'weight', 'level', 'bound', 'contains'])
class Node:
def __init__(self, level, value, weight, bound, contains):
self.level = level
self.value = value
self.weight = weight
self.bound = bound
self.contains = contains
def upper_bound(u, k, n, v, w):
if u.weight > k:
return 0
else:
bound = u.value
wt = u.weight
j = u.level + 1
while j < n and wt + w[j] <= k:
bound += v[j]
wt += w[j]
j += 1
# fill knapsack with fraction of a remaining item
if j < n:
bound += (k - wt) * (v[j] / w[j])
return bound
def knapsack(items, capacity):
item_count = len(items)
v = [0]*item_count
w = [0]*item_count
# sort items by value to weight ratio
items = sorted(items, key=lambda k: k.value/k.weight, reverse = True)
for i,item in enumerate(items, 0):
v[i] = int(item.value)
w[i] = int(item.weight)
q = Queue.Queue()
root = Node(0, 0, 0, 0.0, [])
root.bound = upper_bound(root, capacity, item_count, v, w)
q.put(root)
value = 0
taken = [0]*item_count
best = set()
while not q.empty():
c = q.get()
if c.bound > value:
level = c.level+1
# check 'left' node (if item is added to knapsack)
left = Node(c.value + v[level], c.weight + w[level], level, 0.0, c.contains[:])
left.contains.append(level)
if left.weight <= capacity and left.value > value:
value = left.value
best |= set(left.contains)
left.bound = upper_bound(left, capacity, item_count, v, w)
if left.bound > value:
q.put(left)
# check 'right' node (if items is not added to knapsack)
right = Node(c.value, c.weight, level, 0.0, c.contains[:])
right.contains.append(level)
right.bound = upper_bound(right, capacity, item_count, v, w)
if right.bound > value:
q.put(right)
for b in best:
taken[b] = 1
value = sum([i*j for (i,j) in zip(v,taken)])
return str(value)
我的索引有误吗?我没有正确遍历树或计算边界吗?
bound += v[j]
替换了bound += (k - wt) * (v[j] / w[j])
,显然前者会导致算法过早停止。当我初始化左右节点时,也有一些反向变量(现在已经修复)。现在我卡在了标记哪些物品被取走的问题上。在更大的数据集上,我要么得到[0,1,3,...]
的模式,要么得到[0,2,4,...]
的模式。'contains' 数组更新/修改的位置是否正确? - wikenator