Python中的递归回溯算法

Question

问题：假设你在秤的一侧有一个砝码。给定一组其他权重，看看天平是否平衡。你可以在任何一边使用权重，而不必使用所有权重。

在我当前的解决方案中，每个级别都有3个分支。第一个将数组中的第一个权重添加到“左侧”，第二个简单地丢弃它，第三个将其添加到“右侧”。我的问题似乎是在完成第一个分支之后，如果所有分支都是False，那么它将返回False。相反，我希望它转到下一个分支。在

让我知道的是，当我有weights = [4,1]和{}时，它给了我错误的信息（说它不能被平衡），但是当我把权重的顺序颠倒为[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