关键词：
【中文标题】使用动态编程从 Python 上的子集总和问题中获取所有子集【英文标题】：Getting all subsets from subset sum problem on Python using Dynamic Programming 【发布时间】：2021-12-28 03:54:39 【问题描述】：我正在尝试从元素列表中提取所有子集，这些元素的总和为某个值。
例子-
列表 = [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)
【问题讨论】：
在最坏的情况下，当你有N 零并且所需的总和也为零时，你需要输出所有 2^n - 1 子集 - 所以你不能比 O(2^n) 更好
【参考方案1】：
如果你想输出 所有 个子集，你不能做得比缓慢的 O(2^n) 复杂度更好，因为在最坏的情况下，这将是你的输出大小和时间复杂度是输出大小的下界（这是一个已知的 NP 完全问题）。但是，如果不是返回所有子集的列表，您只想返回一个布尔值，指示是否有可能实现目标总和，或者只是一个子集总和到目标（如果存在），您可以使用动态编程来实现伪-多项式O(nK)时间解，其中n是元素个数，K是目标整数。
DP 方法涉及填写 (n+1) x (K+1) 表，对应表项的子问题为：
DP[i][k] = subset(A[i:], k) for 0 <= i <= n, 0 <= k <= K
也就是说，subset(A[i:], k) 会问，“我可以使用从索引 i 开始的 A 的后缀求和到（小）k 吗？”填满整个表格后，整个问题的答案，subset(A[0:], K) 将在 DP[0][K]
基本情况是 i=n：它们表明如果您使用数组的空后缀，则除了 0 之外，您不能求和
subset(A[n:], k>0) = False, subset(A[n:], k=0) = True
要填表的递归情况有：
subset(A[i:], k) = subset(A[i+1:, k) OR (A[i] <= k AND subset(A[i+i:], k-A[i]))
这只是将您可以使用当前数组后缀和 k 相加的想法，方法是跳过该后缀的第一个元素并使用您在前一行中已有的答案（当第一个元素不在你的数组后缀），或者在你的总和中使用A[i]，并检查你是否可以在前一行中减少总和k-A[i]。当然，您只能在新元素本身不超过您的目标总和的情况下使用它。
例如：子集（A[i:] = [3,4,1,6]，k = 8） 会检查：我是否已经用前一个后缀（A[i+1:] = [4,1,6]）求和到 8？不，或者，我可以使用我现在可用的 3 来求和 8 吗？也就是说，我可以将 k = 8 - 3 = 5 与 [4,1,6] 相加吗？是的。因为至少有一个条件为真，所以我设置 DP[i][8] = True
因为所有基本情况都是针对 i=n 的，并且子集 (A[i:], k) 的递归关系依赖于较小子问题子集 (A[i+i:],. ..)，您从表的底部开始，其中 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)
如果你想在 bool 旁边返回一个实际可能的子集，指示是否可以创建一个，那么对于你的 DP 中的每个 True 标志，你还应该存储让你到达那里的前一行的 k 索引（它将是当前的 k 索引或 kA[i]，具体取决于哪个表查找返回 True，这将指示是否使用了 A[i]）。然后在表格填满后从 DP[0][K] 向后走以获得子集。这使得代码更混乱，但它绝对是可行的。但是，您无法以这种方式获得 所有 个子集（至少不会再次增加您的时间复杂度），因为 DP 表会压缩信息。
【讨论】：
打印总和等于 k 的集合的子集
...ithsumequalstok【发布时间】：2015-02-2106:16:48【问题描述】：动态编程提供了一种非常优雅的解决子集和问题的方法。子集求和问题：求sum=k的子集是否存在。但我看不到如何打印sum=k的所有子集。有关如何修改以下基于动态编程的... 查看详情
为啥我的子集总和方法不正确？
...特别是我很好奇基本想法是否有效，或者我是否应该坚持使用子集和seeyt的正常方法。问题：给定一个数字数组，在数组中找到两个总和相同的子 查看详情
总和小于 M 的大小为 K 的子集的最大总和
...子集中获得的最大和，使得和小于值M？是否有可用的非动态规划解决方案来解决这个问题？或者如果只有dp[i][j][k]只能解决这类问题！你能解释一下算法吗？【问题讨论】：我无法理解 查看详情
在python中查找列表的子集的总和
】在python中查找列表的子集的总和【英文标题】：Findthesumofsubsetsofalistinpython【发布时间】：2011-09-0206:28:41【问题描述】：这可能很简单，我忽略了一些东西......我有一长串整数，在这种情况下代表网站的每日访问者。我想要一... 查看详情
使用 excel vba 宏将总和扩展到动态范围
】使用excelvba宏将总和扩展到动态范围【英文标题】：extendsumtodynamicrangewithexcelvbamacro【发布时间】：2020-09-1509:23:54【问题描述】：我正在尝试将求和公式扩展到动态范围。总和包括从第5行到该列中最后使用的第二行的所有值，... 查看详情
查找总和等于 k 的子集的数量
...发布时间】：2015-03-1113:36:29【问题描述】：谁能解释一下动态算法，它找到总和等于k的子集数。我在谷歌搜索，但找不到任何简单的解释！对不起我的英语不好！代码如下：intnumbers[MAX];intGetmNumberOfSubsets()intdp[MAX];dp[0]=1;intcur 查看详情
带有 2675 个数字列表的子集总和
】带有2675个数字列表的子集总和【英文标题】：SubsetSumwithalistof2675numbers【发布时间】：2017-03-2414:51:06【问题描述】：我正在寻找是否可以有效解决问题的是/否答案。我很确定以我们目前可用的计算技术状态是不可能的。我很高... 查看详情
计算 Mat OpenCV 子集的总和
...【发布时间】：2015-06-1422:11:11【问题描述】：我们可以不使用任何循环直接计算OpenCV(C++)中Mat元素子集的总和吗？示例：Matb_hist，有1列和256行。如何计算0到105行或106到150行的总和？我知道sum(b_hist)会给出整个Mat的总和。我怎样才... 查看详情
从循环 if 语句子集熊猫时间序列数据帧
...一般编程的新手，所以不知道术语是否正确正确。我正在使用Spyder，正在做一个研究项目。我需要在现有数据框(df)中创建一 查看详情
如何递归枚举添加到给定总和的所有子集？
】如何递归枚举添加到给定总和的所有子集？【英文标题】：HowdoIrecursivelyenumerateallsubsetsaddingtoagivensum?【发布时间】：2020-04-1207:34:31【问题描述】：当我尝试获取输出时，它会显示具有相同元素的相同解决方案几次，然后再转到... 查看详情
动态规划算法：硬币的最大总和（小于或等于k）
...等于k的最大可能总和。每个硬币可以根据需要多次使用。如果没有选择硬币，0被认为是最大的。我尝试解决这个问题，我知道这是动态编程，但我无法在 查看详情
计算给定数组的所有子集，总和等于给定总和
】计算给定数组的所有子集，总和等于给定总和【英文标题】：countallsubsetsofgivenarraywithsumequaltogivensum【发布时间】：2020-03-1414:01:20【问题描述】：我可以做些什么来优化这段代码，如果语言是c++，我会更容易理解。给定一个整... 查看详情
使用严格函数式编程从 poset 生成 DAG
】使用严格函数式编程从poset生成DAG【英文标题】：GenerateaDAGfromaposetusingstriclyfunctionalprogramming【发布时间】：2012-02-0823:03:01【问题描述】：这是我的问题：我有一个（非空但可能不是不同的）集合s_i的序列S，并且对于每个s_i，... 查看详情
如何找出为啥所有数据子集的总和比总和小1
】如何找出为啥所有数据子集的总和比总和小1【英文标题】：Howtofindwhysumofallsubsetsofdatais1lessthantotal如何找出为什么所有数据子集的总和比总和小1【发布时间】：2017-06-2802:47:05【问题描述】：我有一些奖励数据。每个奖励或赠款... 查看详情
总和大于或等于 k 的最小子集
】总和大于或等于k的最小子集【英文标题】：Smallestsubsetwithsumgreaterorequaltok【发布时间】：2021-06-0419:10:39【问题描述】：我试图找到一种分而治之的算法来解决O(n)中的这个问题，但我什么也没找到。给定一个数组A和给定值k... 查看详情
改进子集解决方案
...习题，我有一个给定的值和一个给定的数字数组。我可以使用给定数组中的任何值一次来创建等于给定值的总和。原来，我的算法会针对每个可能的组合遍历数组。后来我对其进行了优化，以检查当前总和是否大于该值。如果是... 查看详情
在总和匹配的两组整数中查找子集的算法
】在总和匹配的两组整数中查找子集的算法【英文标题】：Algorithmtofindsubsetwithintwosetsofintegerswhosesumsmatch【发布时间】：2010-10-0110:02:19【问题描述】：我正在寻找一种算法，它可以采用两组整数（正数和负数）并在每组整数中找... 查看详情
子集总和，带有回溯和类
】子集总和，带有回溯和类【英文标题】：SubsetSum,withbacktrackingandclasses【发布时间】：2019-12-0519:34:43【问题描述】：给定一个整数序列和一个数字，程序必须判断该序列中是否有任何组合对数字求和。例如：输入：12345#6输出：... 查看详情