多维背包问题 回溯算法代码

多维背包问题是背包问题的一种扩展，它在每个物品的选择上增加了维度。在传统的背包问题中，每个物品只有一个重量和一个价值，而在多维背包问题中，每个物品有多个属性，比如重量、价值、体积等。

回溯算法是一种穷举搜索的算法，用于解决组合优化问题。下面是多维背包问题的回溯算法代码：

def backtrack(weights, values, capacities, current_weight, current_value, current_capacity, index):
    global max_value
    if index == len(weights):
        if current_value > max_value:
            max_value = current_value
        return

    for i in range(current_capacity // weights[index] + 1):
        if current_weight + i * weights[index] <= capacities[index]:
            backtrack(weights, values, capacities, current_weight + i * weights[index], current_value + i * values[index], current_capacity - i * weights[index], index + 1)

# 示例数据
weights = [2, 3, 4]
values = [4, 5, 6]
capacities = [7, 8, 9]
max_value = 0

backtrack(weights, values, capacities, 0, 0, float('inf'), 0)
print("最大价值为:", max_value)

在上述代码中，`weights`表示每个物品的重量列表，`values`表示每个物品的价值列表，`capacities`表示每个维度的背包容量列表。`current_weight`表示当前已选择的物品的总重量，`current_value`表示当前已选择的物品的总价值，`current_capacity`表示当前剩余的背包容量，`index`表示当前处理的物品索引。

回溯算法通过递归的方式遍历所有可能的解空间，每次选择当前物品的数量，然后继续递归处理下一个物品。当处理完所有物品时，更新最大价值。注意，在每次递归时需要判断当前选择是否符合背包容量的限制。