使用动态规划从 Python 上的子集求和问题中获取所有子集

Question

我正在尝试从元素列表中提取所有子集，这些元素加起来等于某个值。

例子-

列表 = [1,3,4,5,6]
总和 - 9
预期输出 = [[3,6],[5,4]]

已经尝试了不同的方法并获得了预期的输出，但在大量元素上需要花费大量时间。这可以使用动态规划或任何其他技术进行优化吗？

方法一

def subset(array, num):
    result = []
    def find(arr, num, path=()):
        if not arr:
            return
        if arr[0] == num:
            result.append(path + (arr[0],))
        else:
            find(arr[1:], num - arr[0], path + (arr[0],))
            find(arr[1:], num, path)
    find(array, num)
    return result

numbers = [2, 2, 1, 12, 15, 2, 3]
x = 7
subset(numbers,x)

方法 2

def isSubsetSum(arr, subset, N, subsetSize, subsetSum, index , sum):
    global flag
    if (subsetSum == sum):
        flag = 1
        for i in range(0, subsetSize):
            print(subset[i], end = " ")
        print("")
    else:
        for i in range(index, N):
            subset[subsetSize] = arr[i]
            isSubsetSum(arr, subset, N, subsetSize + 1, 
                        subsetSum + arr[i], i + 1, sum)

Answer 1

如果你想输出 all 子集你不能比缓慢的 O(2^n) 复杂度更好，因为在最坏的情况下这将是您的输出和时间复杂度受输出大小的限制（这是一个已知的 NP-Complete 问题）。但是，如果不是 returning 所有子集的列表，您只想 return 一个布尔值，指示是否可以实现目标总和，或者只是一个子集求和到目标（如果存在） , 你可以使用动态规划来求一个伪多项式 O(nK) 时间的解，其中 n 是元素的数量，K 是目标整数。

DP 方法涉及填写 (n+1) x (K+1) table，与 table 的条目对应的子问题是：

DP[i][k] = subset(A[i:], k) for 0 <= i <= n, 0 <= k <= K

也就是subset(A[i:], k)求，'Can I sum to (little) k using the suffix of A starting at index i?'一次填完table，整体问题的答案，subset(A[0: ], K) 将在 DP[0][K]

基本情况适用于 i=n：它们表明如果您使用的是数组的空后缀，则除 0 外不能求和任何值

subset(A[n:], k>0) = False, subset(A[n:], k=0) = True

填写table的递归情况是：

subset(A[i:], k) = subset(A[i+1:, k) OR (A[i] <= k AND subset(A[i+i:], k-A[i]))

这只是将您可以使用当前数组后缀求和为 k 的想法联系起来，方法是跳过该后缀的第一个元素并使用您在上一行中已有的答案（当第一个元素不是' t 在你的数组后缀中），或者在你的总和中使用 A[i] 并检查你是否可以在前一行中减少总和 k-A[i] 。当然，只有当新元素本身不超过你的目标总和时，你才能使用新元素。

ex: 子集 (A[i:] = [3,4,1,6], k = 8) 会检查：我是否已经用前面的后缀 (A[i+1:] = [4,1,6]) 求和到 8？不，或者，我可以使用现在可用的 3 求和为 8 吗？也就是说，我可以用 [4,1,6] 求和为 k = 8 - 3 = 5 吗？是的。因为至少有一个条件为真，所以我设置 DP[i][8] = True

因为所有的基本情况都是i=n，子集(A[i:], k)的递推关系依赖于更小的子问题subset(A[i+i:] ,...)，你从 table 的底部开始，其中 i = n，为每一行填写从 0 到 K 的每个 k 值，然后一直到第 i = 0 行，确保你当您需要时，可以找到较小的子问题的答案。

def subsetSum(A: list[int], K: int) -> bool:
  N = len(A)
  DP = [[None] * (K+1) for x in range(N+1)]
  DP[N] = [True if x == 0 else False for x in range(K+1)]

  for i in range(N-1, -1, -1):
    Ai = A[i]
    DP[i] = [DP[i+1][k] or (Ai <=k and DP[i+1][k-Ai]) for k in range(0, K+1)]

  # print result
  print(f"A = {A}, K = {K}")
  print('Ai,k:', *range(0,K+1), sep='\t')
  for (i, row) in enumerate(DP): print(A[i] if i < N else None, *row, sep='\t')
  print(f"DP[0][K] = {DP[0][K]}")
  return DP[0][K]

subsetSum([1,4,3,5,6], 9)

如果你想 return 一个实际可能的子集与 bool 一起指示是否可以创建一个，那么对于你的 DP 中的每个 True 标志，你还应该存储前一行的 k 索引这让你到达那里（它将是当前的 k 索引或 k-A[i]，取决于哪个 table 查找 returned True，这将指示是否使用了 A[i]）。然后你在table填满后从DP[0][K]向后走得到一个子集。这使代码更加混乱，但它绝对可行。你不能通过这种方式获得 all 子集（至少不会再次增加你的时间复杂度）因为 DP table 压缩信息。

Answer 2

这里是复杂度为O(n^2)的问题的优化解。

def get_subsets(data: list, target: int):
# initialize final result which is a list of all subsets summing up to target
subsets = []

# records the difference between the target value and a group of numbers
differences = {}

for number in data:
    prospects = []

    # iterate through every record in differences
    for diff in differences:

        # the number complements a record in differences, i.e. a desired subset is found
        if number - diff == 0:
            new_subset = [number] + differences[diff]
            new_subset.sort()
            if new_subset not in subsets:
                subsets.append(new_subset)

        # the number fell short to reach the target; add to prospect instead
        elif number - diff < 0:
            prospects.append((number, diff))

    # update the differences record
    for prospect in prospects:
        new_diff = target - sum(differences[prospect[1]]) - prospect[0]
        differences[new_diff] = differences[prospect[1]] + [prospect[0]]
    differences[target - number] = [number]

return subsets

使用动态规划从 Python 上的子集求和问题中获取所有子集

Getting all subsets from subset sum problem on Python using Dynamic Programming

python

algorithm

dynamic-programming

subset-sum

data-structures