分支限界法求解0/1背包问题代码

以下是使用分支限界法求解0/1背包问题的Python代码：

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight

class Node:
    def __init__(self, level, value, weight, items):
        self.level = level
        self.value = value
        self.weight = weight
        self.items = items
    
    def __lt__(self, other):
        return self.value < other.value

def knapsack_bnb(items, capacity):
    items = sorted(items, key=lambda x: x.ratio, reverse=True)
    root = Node(-1, 0, 0, [])
    queue = []
    queue.append(root)
    best_value = 0
    while queue:
        node = queue.pop(0)
        if node.level == len(items) - 1:
            if node.value > best_value:
                best_value = node.value
                best_node = node
        else:
            if node.weight + items[node.level+1].weight <= capacity:
                left_node = Node(node.level+1, node.value+items[node.level+1].value, node.weight+items[node.level+1].weight, node.items+[items[node.level+1]])
                queue.append(left_node)
            bound = bound_value(items, capacity, node)
            if bound > best_value:
                right_node = Node(node.level+1, node.value, node.weight, node.items)
                queue.append(right_node)
    return best_node

def bound_value(items, capacity, node):
    if node.weight >= capacity:
        return 0
    bound = node.value
    j = node.level + 1
    tot_weight = node.weight
    while j < len(items) and tot_weight + items[j].weight <= capacity:
        bound += items[j].value
        tot_weight += items[j].weight
        j += 1
    if j < len(items):
        bound += (capacity - tot_weight) * items[j].ratio
    return bound

# example usage
items = [Item(20, 10), Item(30, 20), Item(66, 30), Item(40, 40), Item(60, 50)]
capacity = 100
best_node = knapsack_bnb(items, capacity)
print("Best value:", best_node.value)
print("Items included:")
for item in best_node.items:
    print("  - value:", item.value, "weight:", item.weight)

在上述代码中，`Item`和`Node`分别表示物品和节点。`knapsack_bnb`函数是求解0/1背包问题的主函数。它首先将物品按照价值重量比从大到小排序，然后从根节点开始，以BFS的方式依次遍历所有子节点。对于每个节点，它有两个子节点，一个是选择当前物品，另一个是不选择当前物品。选择当前物品的子节点的价值和重量是在父节点的基础上加上当前物品的价值和重量，而不选择当前物品的子节点的价值和重量与父节点相同。为了提高效率，在扩展子节点之前，我们首先计算一个上界，如果当前节点的上界小于当前最优解，那么就不需要扩展该节点的右子节点了。`bound_value`函数用于计算节点的上界。

在上述代码的最后，我们用一个例子来演示如何使用该函数。给定5个物品和一个容量为100的背包，我们可以得到最优的价值为146和所选物品为2、3、4、5。