python - Python 中的递归回溯——在秤上平衡重量

Question

问题: 假设您在天平的一侧有一个重量。给定一系列其他重量，看看天平是否会平衡。您可以在任一侧使用权重，而不必使用所有权重。

在我当前的解决方案中，每个级别都有 3 个分支。第一个将数组中的第一个权重添加到“左侧”，第二个简单地将其丢弃，第三个将其添加到“右侧”。我的问题似乎是，完成第一个分支后，如果所有分支都为 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 = []

That cannot be balanced!

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