编辑代码

def knapsack_recursive(capacity, weights, values, n, current_weight, current_value, selected_items, result):
    # 递归终止条件：已经考察完所有商品
    if n == 0:
        result['value'] = max(result['value'], current_value)
        result['items'] = list(selected_items)
        return

    # 尝试放入当前商品
    if current_weight + weights[n - 1] <= capacity:
        selected_items.append(n - 1)
        knapsack_recursive(capacity, weights, values, n - 1,
                           current_weight + weights[n - 1],
                           current_value + values[n - 1],
                           selected_items, result)
        selected_items.pop()  # 回溯，不放入当前商品

    # 不放入当前商品
    knapsack_recursive(capacity, weights, values, n - 1,
                       current_weight, current_value,
                       selected_items, result)

def knapsack_solver(capacity, weights, values):
    result = {'value': 0, 'items': []}
    knapsack_recursive(capacity, weights, values, len(weights), 0, 0, [], result)
    return result

# 商品信息
weights = [4, 3, 1]
values = [3000, 2000, 1500]
capacity = 4

# 求解背包问题
result = knapsack_solver(capacity, weights, values)

# 输出结果
print("Max value:", result['value'])
print("Selected items:", [f"Item {i + 1}" for i in result['items']])