python回溯字典

Question

所以，我总共有n个问题，每个问题都有一些问题。

我要创建的是有u和v问题之间积累x和y点之间问题的所有可能的集合，和我有使用回溯做。为此，我想了解如何使用字典，例如：questions = {“Q1”：5，“Q2”：3，“Q3”：4，“Q4”：10，“Q5”：6，“Q6 “：7}，所以有6个问题，第一个问题（”Q1“）有5个点等等

我开始编码，但我不知道如何创建回溯函数本身，我不明白如果有意义的话，如何去做所有的可能性。

questions = {"Q1":5, "Q2":3, "Q3": 4, "Q4" : 10, "Q5" : 6, "Q6" : 7} 
u = 3 # 
v = 5 # between u and v questions 


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


def get_points(ar): 
    s = 0 
    for key, value in ar.items(): 
     s = s + int(value) 
    return s 


def get_NOQuestions(ar): 
    return len(ar) 



def reject(candidate): 
    if (get_points(candidate) > y and get_NOQuestions(candidate) < v) or (get_NOQuestions(candidate) >= v and get_points(candidate) < x): 
     return False 
    return True 



def accept(candidate): 
    if get_points(candidate) >= x and get_points (candidate) <= y and get_NOQuestions(candidate) >= u and get_NOQuestions(candidate) <= v: 
     return True 
    return False 



def output(candidate): 
    print(candidate) 



ar = {} 

def backtracking(k): 
    for key, value in questions.items(): 
     ar[key] = value 
     if not reject(ar): 
      if accept(ar): 
       output(ar) 
      else: 
       backtracking(k+1) 

backtracking(0) 

这是我这么远，显然是“回溯”功能不起作用，因为它不经过所有的可能性（而不是它应该以这种形式，它只是一个供）

我在考虑可能对字典中的所有项目进行排列（u和v之间的长度排列），并获得满足“接受”函数中条件的条件，但确实有更明智的方法来完成此操作。

Answer 1

您需要重写您的reject()和accept()函数的逻辑，因为您的代码将永远无法达到给定输入的if accept(ar)。试着在纸上运行你的代码，你会发现它。

我也建议重构get_points(arr)到这样的事情：

def get_points(arr): 
    return sum(arr.values()) 

较少的逻辑==更少的错误。