gpt4 book ai didi

algorithm - O(n sqrt(n)) 算法如何在给定数字数组的情况下列出所有可能的总和?

转载 作者:行者123 更新时间:2023-12-04 14:48:01 26 4
gpt4 key购买 nike

我在 Competitive Programming handbook https://cses.fi/book/book.pdf 一书中遇到了一个算法问题。 :整数分区,背包。
问题是:给定一个整数数组,其总和为 n。输出可以使用整数子集形成的所有可能和。
动态规划解决方案是可以理解的。定义 dp(x,k)作为 bool 函数,当我们可以使用第一个 k 时为真相加的数字 x ,否则为假。然后dp(x,k) = dp(x,k-1) | dp(x-A[k],k-1) .复杂度是 O(n^2)。
然而,这本书描述了另一种解决方案,该解决方案利用了数组中不同数字的数量为 O(sqrt (n)) 的事实,然后提到了一个通过将相似数字分组在一起的解决方案。它是如何工作的?这本书似乎很难理解。

最佳答案

我同意作者应该更明确。我的重构是,给定一个元素 a 和一个 (n+1) 元素位数组,指示哪些和可以由先前考虑的元素的子集得出,我们可以在线性时间内计算我们需要的 a 的最小副本数得出一个特定的总和,然后通过我们实际拥有的 a 的副本数量作为阈值。下面的 Python 实现。

import collections
import math


def subset_sums(lst):
n = sum(lst)
dp = [False] * (n + 1)
dp[0] = True
for a, count in collections.Counter(lst).items():
dp = [min_count <= count for min_count in min_counts(dp, a)]
return {x for (x, dp_x) in enumerate(dp) if dp_x}


def min_counts(dp, a):
dp = [(0 if dp_x else math.inf) for dp_x in dp]
for x in range(a, len(dp)):
dp[x] = min(dp[x], dp[x - a] + 1)
return dp


def baseline_subset_sums(lst):
n = sum(lst)
dp = [False] * (n + 1)
dp[0] = True
for a in lst:
for x in range(len(dp) - 1, a - 1, -1):
dp[x] = dp[x] or dp[x - a]
return {x for (x, dp_x) in enumerate(dp) if dp_x}


import random

if __name__ == "__main__":
for rep in range(100000):
rand_lst = [random.randrange(20) for i in range(random.randrange(20))]
assert subset_sums(rand_lst) == baseline_subset_sums(rand_lst), rand_lst

关于algorithm - O(n sqrt(n)) 算法如何在给定数字数组的情况下列出所有可能的总和?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69640627/

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