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

Question

我在 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)) 的事实，然后提到了一个通过将相似数字分组在一起的解决方案。它是如何工作的？这本书似乎很难理解。

Answer 1

我同意作者应该更明确。我的重构是，给定一个元素 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