回溯不尝试所有的可能性

Question

所以我有一个问题列表作为字典，例如

{"Question1": 3, "Question2": 5 ... }

这意味着"Question1"有3分，第二个有5分，依此类推

我正在尝试创建介于一定数量的问题和分数之间的所有问题子集。

我试过

questions = {"Q1":1, "Q2":2, "Q3": 1, "Q4" : 3, "Q5" : 1, "Q6" : 2}
u = 3  #
v = 5 # between u and v questions


x = 5   #
y = 10 #between x and y points


solution = []
n = 0

def main(n_):
        global n
        n = n_

        global solution
        solution = []

        finalSolution = []

        for x in questions.keys():
                solution.append("_")

        finalSolution.extend(Backtracking(0))

        return finalSolution


def Backtracking(k):

        finalSolution = []

        for c in questions.keys():
                solution[k] = c
                print ("candidate: ", solution)
                if not reject(k):
                    print ("not rejected: ", solution)
                    if accept(k):
                                finalSolution.append(list(solution))
                    else:
                                finalSolution.extend(Backtracking(k+1))

        return finalSolution


def reject(k):
    if solution[k] in solution: #if the question already exists
        return True
    if k > v: #too many questions
        return True
    points = 0
    for x in solution:
        if x in questions.keys():
            points = points + questions[x]
    if points > y: #too many points
        return True
    return False



def accept(k):

    points = 0
    for x in solution:
        if x in questions.keys():
            points = points + questions[x]
    if points in range (x, y+1) and k in range (u, v+1):
        return True
    return False


print(main(len(questions.keys())))

但它并没有尝试所有可能性，只是将所有问题放在第一个索引上..

我不知道我做错了什么。

Answer 1

您的代码存在三个问题。

第一个问题是 reject 函数中的第一个检查始终是 True。您可以通过多种方式解决这个问题（您评论说您现在正在使用 solution.count(solution[k]) != 1）。

第二个问题是你的 accept 函数使用变量名 x 来表示它打算成为两个不同的东西（来自 solution 在 for 循环和全局 x 即最小点数）。这是行不通的，当你试图将它传递给 range 时，你会得到一个 TypeError。一个简单的解决方法是重命名循环变量（我建议 q 因为它是 questions 的关键）。检查一个值是否为 in 和 range 也有点尴尬。使用链式比较通常要好得多：if x <= points <= y and u <= k <= v

第三个问题是你根本没有回溯。回溯步骤需要将全局 solution 列表重置为调用 Backtracking 之前的相同状态。您可以在函数末尾执行此操作，就在 return 之前，使用 solution[k] = "_"（您评论说您添加了这一行，但我认为您将其放在了错误的位置）。

无论如何，这是您的函数的固定版本：

def Backtracking(k):
        finalSolution = []
        for c in questions.keys():
                solution[k] = c
                print ("candidate: ", solution)
                if not reject(k):
                    print ("not rejected: ", solution)
                    if accept(k):
                                finalSolution.append(list(solution))
                    else:
                                finalSolution.extend(Backtracking(k+1))
        solution[k] = "_"    # backtracking step here!
        return finalSolution

def reject(k):
    if solution.count(solution[k]) != 1: # fix this condition
        return True
    if k > v:
        return True
    points = 0
    for q in solution:
        if q in questions:
            points = points + questions[q]
    if points > y: #too many points
        return True
    return False

def accept(k):
    points = 0
    for q in solution:  # change this loop variable (also done above, for symmetry)
        if q in questions:
            points = points + questions[q]
    if x <= points <= y and u <= k <= v:  # chained comparisons are much nicer than range
        return True
    return False

那里还有一些可以改进的地方。我认为 solution 是一个具有虚拟值的固定大小的全局列表尤其不符合 pythonic（作为参数传递的动态增长的列表会更自然）。我还建议使用 sum 来累加点，而不是使用你自己的显式循环。

回溯不尝试所有的可能性

backtracking not trying all possibilities

python

backtracking