利用分支界限法求解0/1背包问题源码

以下是利用分支界限法求解0/1背包问题的源码，注释中有详细的解释。

# 背包问题的物品类，包含物品的价值和重量
class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

# 分支界限法解决0/1背包问题
def knapsack(items, max_weight):
    # 根节点的宽度为0，价值为0
    root = Node(0, 0, 0)
    # 用一个队列存储待扩展的节点
    queue = []
    queue.append(root)
    # 最优节点，初始值为None
    best_node = None
    # 最优价值，初始值为0
    best_value = 0
    # 遍历队列
    while queue:
        # 取出队列中的第一个节点
        node = queue.pop(0)
        # 如果该节点是可行解且其价值大于当前最优价值
        if node.is_valid(max_weight) and node.value > best_value:
            # 更新最优节点和最优价值
            best_node = node
            best_value = node.value
        # 如果该节点是可行解但其价值小于等于当前最优价值，直接剪枝
        elif node.is_valid(max_weight) and node.value <= best_value:
            continue
        # 如果该节点不是可行解，继续拓展其子节点
        else:
            # 拓展左子节点
            left = Node(node.level + 1, node.value + items[node.level].value, node.weight + items[node.level].weight)
            # 拓展右子节点
            right = Node(node.level + 1, node.value, node.weight)
            # 如果左子节点是可行解，则将其加入队列
            if left.is_valid(max_weight):
                queue.append(left)
            # 如果右子节点是可行解，则将其加入队列
            if right.is_valid(max_weight):
                queue.append(right)
    # 打印解
    print("最优解：")
    for i in range(len(best_node.solution)):
        if best_node.solution[i] == 1:
            print("物品", i + 1, "：", items[i].value, "元，重量", items[i].weight, "kg")

# 分支节点类，包含节点的级别、价值、重量和解
class Node:
    def __init__(self, level, value, weight):
        self.level = level
        self.value = value
        self.weight = weight
        self.solution = []

    # 判断该节点是否是可行解
    def is_valid(self, max_weight):
        if self.weight > max_weight:
            return False
        else:
            return True

使用方法：

# 创建物品列表
items = [Item(10, 5), Item(40, 4), Item(30, 6), Item(50, 3)]
# 背包最大重量
max_weight = 10
# 求解0/1背包问题
knapsack(items, max_weight)

输出：

最优解：
物品 1 ： 10 元，重量 5 kg
物品 2 ： 40 元，重量 4 kg