用分枝限界法求0/1背包问题python代码

好的，以下是用分枝限界法求0/1背包问题的Python代码：

from queue import Queue

class Node:
    def __init__(self, level, weight, value, include):
        self.level = level
        self.weight = weight
        self.value = value
        self.include = include
        
    def __lt__(self, other):
        return (self.value / self.weight) > (other.value / other.weight)

def bound(node, n, W, weight, value):
    if node.weight >= W:
        return 0
    else:
        i = node.level + 1
        bound_val = node.value
        total_weight = node.weight
        
        while i < n and total_weight + weight[i] <= W:
            total_weight += weight[i]
            bound_val += value[i]
            i += 1
        
        if i < n:
            bound_val += (W - total_weight) * (value[i] / weight[i])
        
        return bound_val

def knapsack(n, W, weight, value):
    q = Queue()
    root = Node(-1, 0, 0, "")
    q.put(root)
    best_node = root
    
    while not q.empty():
        node = q.get()
        if node.include == "":
            left = Node(node.level + 1, weight[node.level], value[node.level], "in")
            right = Node(node.level + 1, 0, 0, "out")
        elif node.include == "in":
            left = Node(node.level + 1, node.weight + weight[node.level], node.value + value[node.level], "in")
            right = Node(node.level + 1, node.weight, node.value, "out")
        else:
            continue
        
        if left.weight <= W and left.value > best_node.value:
            best_node = left
        
        if bound(left, n, W, weight, value) > best_node.value:
            q.put(left)
        
        if bound(right, n, W, weight, value) > best_node.value:
            q.put(right)
    
    return best_node.value

n = int(input("请输入物品数量："))
W = int(input("请输入背包容量："))
weight = []
value = []

for i in range(n):
    w = int(input("请输入第%d个物品的重量：" % (i+1)))
    v = int(input("请输入第%d个物品的价值：" % (i+1)))
    weight.append(w)
    value.append(v)

max_value = knapsack(n, W, weight, value)

print("0/1背包问题的最大价值为：%d" % max_value)

以上代码采用了分枝限界法求解0/1背包问题，使用Python语言编写。输入物品数量、背包容量、以及每个物品的重量和价值，输出最大价值。