0—1背包问题分支限界法代码

下面是0-1背包问题分支限界法的Python代码实现：

from queue import PriorityQueue

class Node:
    def __init__(self, level, value, weight, bound):
        self.level = level
        self.value = value
        self.weight = weight
        self.bound = bound

    def __lt__(self, other):
        return self.bound > other.bound

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

def knapsack(n, W, wt, val):
    pq = PriorityQueue()
    root = Node(-1, 0, 0, 0)
    root.bound = bound(root, n, W, wt, val)
    pq.put(root)
    maxval = 0
    
    while not pq.empty():
        u = pq.get()
        if u.bound > maxval:
            v1 = Node(u.level + 1, u.value + val[u.level + 1], u.weight + wt[u.level + 1], 0)
            v1.bound = bound(v1, n, W, wt, val)
            if v1.weight <= W and v1.value > maxval:
                maxval = v1.value
            if v1.bound > maxval:
                pq.put(v1)
            
            v2 = Node(u.level + 1, u.value, u.weight, 0)
            v2.bound = bound(v2, n, W, wt, val)
            if v2.weight <= W and v2.value > maxval:
                maxval = v2.value
            if v2.bound > maxval:
                pq.put(v2)
    
    return maxval

这个代码实现使用了一个优先队列来管理待处理的节点，并使用一个Node类来表示每个子问题。bound函数用于计算当前节点的上界，knapsack函数实现了整个算法的主要逻辑。