用优先队列式分枝限界法求0/1背包问题python代码

好的，请稍等，让我帮您查询一下资料。

以下是代码示例：

import queue

class Node:
    def __init__(self, level=0, bound=0, weight=0, value=0, items=[]):
        self.level = level
        self.bound = bound
        self.weight = weight
        self.value = value
        self.items = items

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

def bound(node, n, W, wt, val):
    if (node.weight >= W): # 超过容量，无法继续扩展节点
        return 0
    else:
        nextIdx = node.level + 1
        bound = node.value
        totWeight = node.weight

        while (nextIdx < n and totWeight + wt[nextIdx] <= W):
            totWeight += wt[nextIdx]
            bound += val[nextIdx]
            nextIdx += 1

        if (nextIdx < n):
            bound += (W - totWeight) * (val[nextIdx] / wt[nextIdx])

        return bound

def solveKnapsack(W, wt, val, n):
    pq = queue.PriorityQueue()
    root = Node(-1, 0, 0, 0, [])
    root.bound = bound(root, n, W, wt, val)
    pq.put(root)
    maxVal = 0
    maxItems = []

    while (not pq.empty()):
        top = pq.get()

        if (top.bound > maxVal):
            left = Node(top.level + 1, 0, top.weight, top.value, top.items.copy())
            left.bound = bound(left, n, W, wt, val)

            if (left.bound > maxVal):
                pq.put(left)

            if (left.value > maxVal):
                maxVal = left.value
                maxItems = left.items

            right = Node(top.level + 1, 0, top.weight + wt[top.level + 1], top.value + val[top.level + 1], top.items.copy())
            right.items.append(top.level + 1)
            right.bound = bound(right, n, W, wt, val)

            if (right.bound > maxVal):
                pq.put(right)

            if (right.value > maxVal):
                maxVal = right.value
                maxItems = right.items

    return (maxVal, maxItems)

摘自：https://zhuanlan.zhihu.com/p/35427648