Python中的递归回溯——天平上的平衡重量

Question

问题： 假设你有一个秤的一边放着一个重物。给定一组其他的重物，看看这个秤是否能平衡。你可以在任意一边使用这些重物，而且不需要用完所有的重物。

在我现在的解决方案中，每一层有三个选择。第一个选择是把数组中的第一个重物放到“左边”，第二个选择是直接不使用这个重物，第三个选择是把它放到“右边”。我遇到的问题是，在完成第一个选择后，如果所有的选择结果都是 False，它就会返回 False。但我希望它能继续检查下一个选择。

让我意识到这个问题的原因是，当我有 weights = [4,1] 和 init_weight = 3 时，它给了我错误的提示（说无法平衡），但当我把重物的顺序改成 [1,4] 时，它就给了我正确的提示。

我昨天刚开始学习Python，所以我猜我可能遗漏了一些语法上的细节。不过，这肯定也不排除算法上的问题！

def balanceable_rec(L, R, weights):

    print("L =", L, "  R =", R, "  weights =", weights)

    if (L == 0  or  L==R  or L in weights):
        return True
    if (len(weights) == 0):
        return False

    w = weights.pop(0)
    if balanceable_rec(L + w, R, weights):  return True
    if balanceable_rec(L, R, weights):      return True
    if balanceable_rec(L, R + w, weights):  return True

    return False


def balanceable(w, weights):
    return balanceable_rec(w, 0, weights)


# ----------------------

# weights = [1,4]
weights = [4,1]
init_weight = 3

if (balanceable(init_weight, weights)):     print("That can be balanced!")
else:           print("That cannot be balanced!")

这是输出结果：

L = 3 R = 0 weights = [4, 1]

L = 7 R = 0 weights = [1]

L = 8 R = 0 weights = []

L = 7 R = 0 weights = []

L = 7 R = 1 weights = []

L = 3 R = 0 weights = []

L = 3 R = 4 weights = []

这无法平衡！

Answer 1

你需要在递归调用中传递weights的副本，这样在调用pop的时候就不会影响到原来的weights对象。例如：

def balanceable_rec(L, R, weights):

    print("L =", L, "  R =", R, "  weights =", weights)

    if (L == 0  or  L==R  or L in weights):
        return True
    if (len(weights) == 0):
        return False

    w = weights.pop(0)
    if balanceable_rec(L + w, R, weights[:]):  return True
    if balanceable_rec(L, R, weights[:]):      return True
    if balanceable_rec(L, R + w, weights[:]):  return True

    return False