问题标签 [subset-sum]

我有一个与子集和问题有关的问题，我想知道这些差异是否使它更容易，即可以在合理的时间内解决。

给定一个值 V、一个集合大小 L 和一个数字序列 [1,N] S，S 中有多少个大小为 L 的子集总和小于 V？

这在三个方面不同于子集和问题：

1. 我关心有多少子集小于给定值，而不是有多少相等。
2. 子集大小是固定的。
3. 我关心有多少集合总和小于 V，而不仅仅是是否存在。

有没有合理有效的算法来解决这个问题？

编辑：显然，这可以使用组合生成算法在 O(N choose L) 中完成。我真正感兴趣的是可以显着加快速度的巧妙技巧。

我正在寻找一种算法，它可以采用两组整数（正数和负数）并在每个整数中找到具有相同总和的子集。

这个问题类似于子集和问题，除了我在两边都寻找子集。

这是一个例子：

列表 A {4, 5, 9, 10, 1}

列表 B {21, 7, -4, 180}

所以这里唯一的匹配是：{10, 1, 4, 9} <=> {21, 7, -4}

有谁知道是否有针对此类问题的现有算法？

到目前为止，我唯一的解决方案是一种蛮力方法，它尝试每种组合，但它在指数时间内执行，我不得不对要考虑的元素数量进行严格限制，以避免花费太长时间。

我能想到的唯一其他解决方案是在两个列表上运行阶乘并在那里寻找相等性，但这仍然不是很有效，并且随着列表变大，需要的时间呈指数增长。

首先：我不是程序员，从未学过编程/算法。实际上我必须编程，主要是在 awk 或 ruby​​ 中，一些 bash。

在今天的任务中，我在纯文本文件中有一个巨大的数据集（浮点数），一个记录/行，以及集合中所有数字的总和，但是总和是错误的，因为有些数字（只能一）在集合中是负数，但我们在文件中看不到它（如果元素是负数，则没有符号）。

但我必须找到它/他们：所以首先我计算了正确的总和（将所有数字与 相加awk）并不关心他们的迹象。现在我现在是原始总和（关心符号）和我的新总和之间的差异。但我必须找到数据集的所有子集，它们的和与差/2 完全相同。

例如：

现在我们可以计算 1+2+3+4+5 - ORIG SUM 之间的差值：15-5=10。10/2 = 5，所以我需要找到所有可以加起来为5的子集，即[1,4]，[2,3]，[5]。

有正确的方法吗？我更喜欢 awk、ruby、shell 脚本，但 python 和 perl 都是可以接受的（没有大量使用外部库，因为我无权安装它们）。

提前致谢。

The problem is the following:

You are given a set of positive integers { a1 , a2 , a3 , ... , an } in which there are no same numbers ( a1 exists only once ,a2 exists only once,...) eg A = {12 , 5 ,7 ,91 }. Question: Are there two disjoint subsets of A , A1 = { b1,b2,...,bm } and A2 = { c1,c2,...,ck} so that b1+b2+...+bm = c1+c2+...+ck ?

Note the following: It is not obligatory for A1 and A2 to cover A, so the problem isn't automatically reduced to the subset sum problem. eg A = {2,5,3,4,8,12} A1= {2,5} so sum of A1 is 7 A2= {3,4} so sum of A2 is 7 We found two disjoint subsets of A with the described property so the problem is solved.

How can I solve this problem? Can I do something better than find all possible (disjoint)subsets, calculate their sums and find two equal sums?

Thank you for your time.

我用 C++ 编写了一个循环来给我 6 个随机数并将它们存储在一个数组中。我想做的是对数组的元素求和，直到我得到一个大于数字“x”的值，但我想这样做而不必添加所有元素。目标是找到总和为 x 值的第一个元素。

例如，数组是[1,2,3,4,5,6]，和x = 6，所以我要寻找的是元素[1,2,3]。

我查看了标准库并尝试使用“valarray”中的 sum 函数，但这只是给出了所有元素的总和。任何关于如何成功编码的想法将不胜感激。

我发布这篇文章的原因是我希望核对客户应收帐款帐户，其中“付款”已过帐到帐户，而不是与未结发票匹配并清算。所以这是我的问题：

有一个数字（付款），应该等于给定数字集（发票金额）的子集。简单的例子：

付款 $10,002

发票值：

5001 2932 876 98 21 9923 2069 123 432 765

我想要一种方法从这个集合中取出 5001、293​​2 和 2069。

作为非程序员，Excel 电子表格应用程序对我来说是最容易创建的。想法？

我正在尝试对我的 TI-83 进行编程以进行子集总和搜索。所以，给定一个长度为 N 的列表，我想找到所有给定长度 L 的列表，总和为给定值 V。

这与常规子集和问题有点不同，因为我只搜索给定长度的子集，而不是所有长度，并且递归不一定是首选，因为我无法调用我正在工作的程序。

我可以使用嵌套循环轻松完成任务，但是对于大于 5 的 L 值，这变得很麻烦。我正在尝试动态解决方案，但没有得到任何结果。

真的，在这一点上，我只是想让列表引用正确，所以这就是我正在寻找的。让我们举个例子：

所以

让我们寻找长度为 3 的所有子集以使其相对较短，因此 L = 3（6c3 = 20 个总输出）。

理想情况下，要搜索的列表引用是：

显然是通过以下方式完成的：

我最初对 N 的数据进行降序排序，这允许我搜索缩短搜索的条件，并且当我在循环中增加 A、B 和 C 的值时，使用 FOR 循环在不同的地方把它搞砸了。

我也在寻找更好的动态解决方案。我已经在网络上进行了一些研究，但我似乎无法根据我的特定情况调整那里的内容。

任何帮助，将不胜感激。我试图保持足够简短，以免写小说，而是解释我想要了解的内容。我可以根据需要提供更多详细信息。

您可能知道，SUBSET-SUM问题被定义为确定一组整数的子集是否与指定的整数相加。（还有另一个子集和定义，其中一组整数和为零，但我们现在使用这个定义）

例如((1,2,4,5),6)是true因为(2,4)总和6。我们说这(2,4)是一个"solution"

此外，((1,5,10),7)是false因为论点中没有任何内容总和7

我的问题是，给定一组参数数字，SUBSET-SUM是否存在可能解决方案数量的多项式上限。在第一个示例中，有(2,4)和(1,5)。

我们知道，既然SUBSET-SUM在多项式时间内确定 NP 完全可能是不可能的。但是我的问题与决策时间无关，我严格询问解决方案列表的大小。

显然，参数数的幂集的大小可以是解决方案列表大小的上限，但是这具有指数增长。我的直觉是应该有一个多项式界限，但我无法证明这一点。

nb我知道这听起来像是一个家庭作业问题，但请相信我不是。我正在尝试自学 CS 理论的某些方面，这就是我的想法。

给定一组正整数，我想要那些整数的子集，其总和是超过阈值的最小总和。

当我想出一个似乎是解决它的通用算法时，我正在阅读子集和问题：

“set”是一个不包含重复项的列表，“sum”是搜索子集的总和。“subsets”是一个 cons 单元的列表，其中“car”是一个子集列表，“cdr”是该子集的总和。只需将元素放在前面，就可以在 O(1) 时间内从旧子集创建新子集。

我不确定它的运行时复杂性是多少，但似乎随着每个元素“总和”的增长，“子集”的大小加倍，加一，所以在我看来至少是二次的。

我发布这个是因为我之前的印象是 NP 完全问题往往是棘手的，并且通常可以希望的最好的问题是启发式的，但这似乎是一个通用的解决方案，假设你有 CPU 周期，总是给你正确的答案。像这样可以解决多少其他 NP 完全问题？