gpt4 book ai didi

python - 给定总和的最短子集和 Python 中最快的解决方案

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:44:41 27 4
gpt4 key购买 nike

这是 "given sum problem" 的变体我尝试用 Python 编写一个解决方案,它将在 O(log n) 时间内解决它。对于给定的自然数 N (等于或大于 1) 找到项目的最短计数 p1.. n 总和构成 N,而 p 项是以下迭代的产物:

pi 的值是pi-1* 2pi-1+ 1

p1 开始,正好是 1

相应地:

p2 总是 2,但是 p3 可以是 3 或 4

对于输入N = 18,候选集为:[1, 2, 4, 5, 6], [1, 2, 3, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3, 4, 8]

答案是 5

这是我到目前为止编写的代码,但它很慢并且在适度“大”(N >= 1000)值时卡住:

possible = None


def solution(N):
global possible
possible = list()
tea(1, [1], N)
sizes = [len(p) for p in possible]
return min(sizes)
pass


def tea(n, l, target):
global possible
if (sum(l) > target):
return
elif (sum(l) == target):
possible.append(l)
i = n * 2
tea(i, l + [i], target)
i = n + 1
tea(i, l + [i], target)

print solution(18)
# should print 5
print solution(220)
# should print 11
print solution(221)
# no such solution? print -1

如何更高效的解决?

最快的解决方案是最重要的,但更 pythonic 的代码也是值得赞赏的。

最佳答案

使用广度优先搜索减少无用功。下面的代码可以进一步优化。

def solution(n):
q = [(1,)]
visited = set()
for seq in q:
s = sum(seq)
if s == n:
return seq
elif s > n:
continue
key = (seq[-1], s)
if key in visited:
continue
visited.add(key)
q.append(seq + (seq[-1] * 2,))
q.append(seq + (seq[-1] + 1,))
return None

关于python - 给定总和的最短子集和 Python 中最快的解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31003685/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com