01背包问题回溯法python

好的，下面是一个使用回溯法解决01背包问题的Python代码示例：

def backtrack_01knapsack(values, weights, capacity, cur_weight, cur_value, index):
    """
    回溯法解决01背包问题
    :param values: 物品价值列表
    :param weights: 物品重量列表
    :param capacity: 背包容量
    :param cur_weight: 当前已装进背包的重量
    :param cur_value: 当前已装进背包的价值
    :param index: 当前考虑到的物品下标
    :return: 最大价值
    """
    if index == len(values) or cur_weight == capacity:
        # 达到物品列表末尾或背包已满，返回当前已装进背包的价值
        return cur_value
    else:
        # 不选当前物品
        max_value = backtrack_01knapsack(values, weights, capacity, cur_weight, cur_value, index + 1)
        if cur_weight + weights[index] <= capacity:
            # 选当前物品
            max_value = max(max_value, backtrack_01knapsack(values, weights, capacity, cur_weight + weights[index],
                                                           cur_value + values[index], index + 1))
        return max_value

可以通过调用该函数来求解01背包问题的最大价值，例如：

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
max_value = backtrack_01knapsack(values, weights, capacity, 0, 0, 0)
print(max_value)  # 输出结果为220

这里以一个简单的示例来说明，物品列表包含三个物品，分别的价值为60、100、120，重量分别为10、20、30，背包容量为50，求解最大价值。