gpt4 book ai didi

python - 分而治之以找到列表的最大和子列表

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:09:22 26 4
gpt4 key购买 nike

给定一个列表L,列表中相邻的两项不能同时在子列表S中被选取,并且列表L不包含重复值。我想使用分而治之的方法设计一种算法,该算法输出一个子列表 S,该子列表 S 最大化其元素的总和。例如,如果 L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13],则 S = [1, 5, 7, 15, 13]。我编写的以下代码不起作用,我认为这不是分而治之的方法。

def bestsublist(l):
sublist = []
n = len(l)
totalsum = [None] * (n + 1)
totalsum[n] = 0
for i in range(n-1,-1,-1):
totalsum[i] = max(l[i] + totalsum[min(i+2,n)],totalsum[min(i+1,n)])
if l[i] + totalsum[min(i+2,n)] > totalsum[min(i+1,n)]:
sublist.append(l[l[i] + totalsum[min(i+2,n)] - 1])
else:
sublist.append(l[totalsum[min(i+1,n)] - 1])

return sublist

最佳答案

您的解决方案几乎是正确的。唯一的问题在于您构建解决方案子列表的方式。

问题是您在完成遍历整个列表之前附加到它,所以您还不知道是否要使用该元素。

所以要修复它只需再次运行列表并构建子列表。这是它的样子:

....
for i in range(n-1,-1,-1):
totalsum[i] = max(l[i] + totalsum[min(i+2,n)],totalsum[min(i+1,n)])

i = 0
while i < n:
if l[i] + totalsum[min(i+2,n)] > totalsum[min(i+1,n)]:
sublist.append(l[i])
i += 2
else:
i += 1
return sublist

附言您的解决方案是动态规划,而不是分而治之。

关于python - 分而治之以找到列表的最大和子列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52147351/

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