背包问题回溯法非递归

背包问题是一个经典的组合优化问题，其中给定一组物品和一个背包，每个物品都有自己的重量和价值。目标是找到一种最佳的方式将物品放入背包中，使得背包中物品的总价值最大，同时不能超过背包的容量限制。

背包问题可以使用回溯法来解决，回溯法是一种通过穷举所有可能的解来找到最优解的方法。下面是背包问题的回溯法非递归实现的示例代码：

def knapsack_non_recursive(weights, values, capacity):
    n = len(weights)
    best_value = 0
    best_solution = [0] * n
    stack = [(0, 0, 0, [])]  # (当前物品索引, 当前重量, 当前价值, 当前解)

    while stack:
        i, cur_weight, cur_value, cur_solution = stack.pop()

        if i == n:
            if cur_value > best_value:
                best_value = cur_value
                best_solution = cur_solution
        else:
            # 不放入当前物品
            stack.append((i + 1, cur_weight, cur_value, cur_solution))

            # 放入当前物品
            if cur_weight + weights[i] <= capacity:
                stack.append((i + 1, cur_weight + weights[i], cur_value + values[i], cur_solution + [i]))

    return best_value, best_solution

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

best_value, best_solution = knapsack_non_recursive(weights, values, capacity)
print("Best value:", best_value)
print("Best solution:", best_solution)

这段代码使用一个栈来模拟递归的过程，通过不断地将下一个状态压入栈中，直到找到最优解为止。在每个状态中，我们可以选择放入当前物品或者不放入当前物品，然后继续向下搜索。