01背包问题的回溯算法代码

01背包问题是一个经典的动态规划问题，可以用回溯法来解决，尤其是在物品的价值和重量不是整数的情况下。以下是使用Python编写的一个基本的回溯算法示例：

def knapsack(capacity, weights, values, n):
    def backtrack(i, cur_weight):
        nonlocal max_value

        # 如果达到物品结束，考虑当前背包状态是否最优
        if i == n:
            if cur_weight <= capacity and max_value < cur_value + total_values[i]:
                max_value = cur_value + total_values[i]
                optimal_solution.append((weights[i], values[i]))

        # 否则，尝试加入或不加入当前物品
        else:
            # 加入物品
            backtrack(i + 1, cur_weight + weights[i])
            
            # 不加入物品，保持背包重量不变
            backtrack(i + 1, cur_weight)

    max_value = 0
    optimal_solution = []
    total_values = [values[i] for i in range(n)]  # 物品总价值数组

    # 回溯开始，从第一个物品开始
    backtrack(0, 0)
    return max_value, optimal_solution

# 示例调用
capacity = 50
weights = [10, 20, 30]
values = [60, 100, 120]
n = len(weights)
max_value, solution = knapsack(capacity, weights, values, n)
print("最大价值:", max_value)
print("解决方案:", solution)