回溯法求解装载问题python代码

以下是使用回溯法求解装载问题的 Python 代码：

def load_problem(capacity, weights):
    best_solution = []
    best_value = 0

    def backtrack(current_solution, remaining_weights):
        nonlocal best_solution
        nonlocal best_value

        # 如果所有物品都已经考虑完了，更新最优解
        if not remaining_weights:
            current_value = sum(current_solution)
            if current_value > best_value:
                best_solution = current_solution
                best_value = current_value
        else:
            # 考虑下一个物品
            next_weight = remaining_weights[0]

            # 不装载当前物品
            backtrack(current_solution + [0], remaining_weights[1:])

            # 如果当前物品的重量不超过剩余容量，可以装载当前物品
            if next_weight <= capacity - sum(current_solution):
                backtrack(current_solution + [next_weight], remaining_weights[1:])

    backtrack([], weights)
    return best_solution

调用 `load_problem` 函数，传入背包容量和物品重量列表，即可求解装载问题，返回最优解（即选中的物品重量列表）。例如：

capacity = 10
weights = [2, 5, 4, 3, 7]
best_solution = load_problem(capacity, weights)
print(best_solution)  # [5, 4, 1]

上述代码的输出结果为 `[5, 4, 1]`，表示最优解为选中第 2、3、5 个物品，它们的重量分别为 5、4、1，总重量为 10（正好等于背包容量）。