我花了一个星期的时间在这个分支上工作并为背包问题绑定了代码，我查看了很多关于这个主题的文章和书籍。但是，当我运行我的代码时，我没有得到我期望的结果。从文本文件接收输入，例如：
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)
我的指数是否关闭？我没有正确遍历树或计算边界吗？
我想如果你不拿这个项目，你只想计算界限。如果你拿走这个项目，那就意味着你的约束仍然可以实现。如果你不这样做，你必须重新调整你的期望。
def upper_bound(u, k, n, v, w):
if u.weight > k:
return 0
else:
bound = u.value
wt = u.weight
j = u.level
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) * float(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: float(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(level,c.value + v[level-1], c.weight + w[level-1], 0.0, c.contains[:])
left.bound = upper_bound(left, capacity, item_count, v, w)
left.contains.append(level)
if left.weight <= capacity:
if left.value > value:
value = left.value
best = set(left.contains)
if left.bound > value:
q.put(left)
# check 'right' node (if items is not added to knapsack)
right = Node(level,c.value, c.weight, 0.0, c.contains[:])
right.bound = upper_bound(right, capacity, item_count, v, w)
if right.weight <= capacity:
if right.value > value:
value = right.value
best = set(right.contains)
if right.bound > value:
q.put(right)
for b in best:
taken[b-1] = 1
value = sum([i*j for (i,j) in zip(v,taken)])
return str(value)
import functools
class solver():
def __init__(self, Items, capacity):
self.sortedItems = list(filter(lambda x: x.value > 0, Items))
self.sortedItems = sorted(self.sortedItems, key=lambda x:float(x.weight)/float(x.value))
self.numItems = len(Items)
self.capacity = capacity
self.bestSolution = solution(0, self.capacity)
def isOptimisitcBetter(self, sol, newItemIdx):
newItem = self.sortedItems[newItemIdx]
rhs = (sol.value + (sol.capacity/newItem.weight)*newItem.value)
return rhs > self.bestSolution.value
def explore(self, sol, itemIndex):
if itemIndex < self.numItems:
if self.isOptimisitcBetter(sol, itemIndex):
self.exploreLeft(sol, itemIndex)
self.exploreRight(sol, itemIndex)
def exploreLeft(self, sol, itemIndex):
newItem = self.sortedItems[itemIndex]
thisSol = sol.copy()
if thisSol.addItem(newItem):
if thisSol.value > self.bestSolution.value:
self.bestSolution = thisSol
self.explore(thisSol, itemIndex+1)
def exploreRight(self, sol, itemIndex):
self.explore(sol, itemIndex+1)
def solveWrapper(self):
self.explore(solution(0, self.capacity), 0)
class solution():
def __init__(self, value, capacity, items=set()):
self.value, self.capacity = value, capacity
self.items = items.copy()
def copy(self):
return solution(self.value, self.capacity, self.items)
def addItem(self, newItem):
remainingCap = self.capacity-newItem.weight
if remainingCap < 0:
return False
self.items.add(newItem)
self.capacity = remainingCap
self.value+=newItem.value
return True
solver = solver(items, capacity)
solver.solveWrapper()
bestSol = solver.bestSolution