我对下面的问题感兴趣主要是为了获得关于回溯算法的直觉,所以我不是在寻找不使用回溯的替代解决方案。你知道吗
问题:找到所有n个元素向量,使它们的元素之和小于或等于某个数字K。向量中的每个元素都是整数。
示例:如果n=3,K=10,则[9,0,0]和[5,0,5]是解,而[3,1,8]不是。你知道吗
从this site开始,我修改了python代码,试图实现一个解决方案。你知道吗
以下是一般的“回溯引擎”功能:
def solve(values, safe_up_to, size):
solution = [None] * size
def extend_solution(position):
for value in values:
solution[position] = value
if safe_up_to(solution, position):
if position >= size-1 or extend_solution(position+1):
return solution
return None
return extend_solution(0)
下面是检查解决方案是否“安全”的函数:
def safe_up_to(partial_solution, target = 100):
partial_solution = np.array(partial_solution) # convert to np array
# replace None with NaN
partial_solution = np.where(partial_solution == None, np.nan, partial_solution)
if np.nansum(partial_solution) <= target:
return True
else:
return False
然而,当我同时运行这两个函数时,我只得到一个全为零的向量。你知道吗
solve(values=range(10), safe_up_to=safe_up_to, size=5)
我应该如何修改此代码以获得所有可行的解决方案?你知道吗
下面是您的代码的一个稍微修改过的版本。我试着让它尽可能少的改变:
印刷品:
相关问题 更多 >
编程相关推荐