def backtrack_knapsackweights values capacity def backtracki current_weight current_value nonlocal max_value if current_weight capacity return if current_value max

def backtrack_knapsack(weights, values, capacity): def backtrack(i, current_weight, current_value): nonlocal max_value if current_weight > capacity: # 如果当前重量超过背包容量，则返回 return if current_value > max_value: # 如果当前价值大于最大价值，则更新最大价值 max_value = current_value if i == n: # 如果已经遍历完所有物品，则返回 return backtrack(i + 1, current_weight, current_value) # 不选择当前物品，继续遍历下一个物品 backtrack(i + 1, current_weight + weights[i], current_value + values[i]) # 选择当前物品，更新当前重量和价值

n = len(weights)  # 物品的数量
max_value = 0  # 最大价值
backtrack(0, 0, 0)  # 从第一个物品开始进行回溯
return max_value  # 返回最大价值