python利用分支界限法解决0/1背包问题代码

以下是一个简单的 Python 代码来使用分支界限法解决0/1背包问题：

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

def solve_knapsack(items, max_weight):
    n = len(items)
    # 初始化第一行和第一列为0
    table = [[0 for _ in range(max_weight + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, max_weight + 1):
            # 如果当前物品的重量超过了容量，则不取该物品
            if items[i - 1].weight > j:
                table[i][j] = table[i - 1][j]
            else:
                # 否则，比较不取该物品和取该物品二者的价值
                table[i][j] = max(table[i - 1][j], table[i - 1][j - items[i - 1].weight] + items[i - 1].value)
    return table[-1][-1]

if __name__ == '__main__':
    items = [Item(2, 5), Item(3, 8), Item(4, 10), Item(5, 12)]
    max_weight = 9
    max_value = solve_knapsack(items, max_weight)
    print("Maximum value of items that can be carried:", max_value)

在这个例子中，我们将一个 2, 5 重量/价值对，一个 3, 8 重量/价值对，一个 4, 10 重量/价值对和一个 5, 12 重量/价值对添加到模拟的背包中，最大容量为 9。该程序使用分支界限法，计算最大价值，打印出结果 13。