我很乐意得到一些帮助。
我有以下问题:
我得到了一个数字列表seq
和一个目标数字,我需要写两件事:
-
返回的递归解决方案True
如果存在等于目标数的子序列之和并且False
否则。
例子:
subset_sum([-1,1,5,4],0) # True
subset_sum([-1,1,5,4],-3) # False
其次,我需要使用我在上一个解决方案中编写的内容来编写一个解决方案
但现在记忆化使用字典,其中键是元组:(len(seq),target)
对于第一点,这是我到目前为止所得到的:
def subset_sum(seq, target):
if target == 0:
return True
if seq[0] == target:
return True
if len(seq) > 1:
return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target)
return False
不确定我是否正确,所以如果我能得到一些意见,我将不胜感激。
对于数字 2:
def subset_sum_mem(seq, target, mem=None ):
if not mem:
mem = {}
key=(len(seq),target)
if key not in mem:
if target == 0 or seq[0]==target:
mem[key] = True
if len(seq)>1:
mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem)
mem[key] = False
return mem[key]
我无法通过记忆来给我正确的答案,所以我很高兴在这里得到一些指导。
感谢任何愿意提供帮助的人!
仅供参考,这是使用动态规划的解决方案:
def positive_negative_sums(seq):
P, N = 0, 0
for e in seq:
if e >= 0:
P += e
else:
N += e
return P, N
def subset_sum(seq, s=0):
P, N = positive_negative_sums(seq)
if not seq or s < N or s > P:
return False
n, m = len(seq), P - N + 1
table = [[False] * m for x in xrange(n)]
table[0][seq[0]] = True
for i in xrange(1, n):
for j in xrange(N, P+1):
table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]]
return table[n-1][s]
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)