我的函数应该找出数字列表的值是否以任何方式或形式加起来符合我的目标。我的代码是:
def memoizedSubset(target, numberList, memo):
''' Returns True if there exists a subset of numberList that adds
up to target and returns False otherwise.'''
if target == 0:
return True;
elif numberList == ():
return False;
elif (target, numberList) in memo:
return memo[(target, numberList)];
elif numberList[0] > target:
solution = memoizedSubset(target, numberList[1:], memo);
memo[(target, numberList)] = solution;
return solution;
else:
useIt = memoizedSubset(target - numberList[0], numberList, memo);
loseIt = memoizedSubset(target, numberList[1:], memo);
solution = useIt or loseIt;
memo[(target, numberList)] = solution;
return solution;
numberTuple = tuple(range(2, 100, 2));
print(memoizedSubset(1234567, numberTuple, {}));
逻辑似乎完美无缺,但当我尝试运行该函数时,我得到了最大递归深度已达到错误。我使用字典来加速这个过程,因为如果没有字典,给定的值需要一段时间才能完成。我终生无法弄清楚问题出在哪里。
更新:该代码适用于较小的值,但不适用于较大的值,如上面的 1234567。记忆化难道不应该克服递归限制的驼峰吗?
请您参考如下方法:
删除内存逻辑并在函数顶部添加 print(target, numberList[:5]) 得到:
(1234567, (2, 4, 6, 8, 10))
(1234565, (2, 4, 6, 8, 10))
(1234563, (2, 4, 6, 8, 10))
(1234561, (2, 4, 6, 8, 10))
(1234559, (2, 4, 6, 8, 10))
(1234557, (2, 4, 6, 8, 10))
(1234555, (2, 4, 6, 8, 10))
(1234553, (2, 4, 6, 8, 10))
...
Traceback (most recent call last):
File "/Users/raymond/Documents/tmp3.py", line 22, in <module>
print(memoizedSubset(1234, numberTuple, {}));
File "/Users/raymond/Documents/tmp3.py", line 16, in memoizedSubset
useIt = memoizedSubset(target - numberList[0], numberList, memo);
这表明递归进行得太慢以至于无法工作。
即使添加 sys.setrecursionlimit(10000) 也不能缓解问题。
调试代码:
import sys
sys.setrecursionlimit(10000)
def memoizedSubset(target, numberList, memo):
''' Returns True if there exists a subset of numberList that adds
up to target and returns False otherwise.'''
print(target, numberList[:5])
if target == 0:
return 0;
elif numberList == ():
return False;
elif numberList[0] > target:
solution = memoizedSubset(target, numberList[1:], memo);
return solution;
else:
useIt = memoizedSubset(target - numberList[0], numberList, memo);
loseIt = memoizedSubset(target, numberList[1:], memo);
solution = useIt or loseIt;
return solution;
numberTuple = tuple(range(2, 100, 2));
print(memoizedSubset(1234567, numberTuple, {}));
