问题标签 [subset-sum]

我在一次采访中遇到了以下问题，尽管我给出了一个可行的实现，但它的效率还不够高。

数组 A 的切片是满足 0 ≤ P ≤ Q < N 的任意整数对 (P, Q)。如果数字 A[P] + A[P +1] + ... + A[Q−1] + A[Q] 可以被 K 整除。

我被要求编写的函数必须返回可被 K 整除的切片数。预期的时间复杂度为 O(max(N, K))，空间复杂度为 O(K)。

我的解决方案是最简单的，一个循环在另一个循环中检查每个切片：O(n^2)

我一直在想，但我真的不知道如何在 O(max(N, K)) 中做到这一点。

它可能是子集和问题的变体，但我不知道如何计算每个子数组。

编辑：数组中的元素可能是负数。这是一个例子：

我有一个问题，它是 NP 完全的分区问题的变体。这是一个优化问题，而不是一个决策问题。

问题：将一个数字列表划分为两个子集，使它们的总和之差最小，然后找到这两个子集。如果n是偶数，那么大小应该是n/2，如果是奇数，那么floor[n/2]和ceil[n/2]。

假设伪多项式时间 DP 算法最适合精确解，如何修改它来解决这个问题？解决这个问题的最佳近似算法是什么？

我有一个 N 个正整数的集合，每个正整数都以一个（相对较小的）常数 C 为界。我想找到这些数字的一个子集，其中最小的总和大于（或等于）一个值 K。

涉及的数字不是很大（<100），但即使在最坏的情况下我也需要良好的性能。我想也许我可以让 Pisinger 的动态规划算法适应这项任务；它在 O(NC) 时间内运行，我碰巧满足有界正数的要求。

[编辑]：数字未排序，可能有重复。

但是，我对算法的理解不够好，无法自己做到这一点。事实上，我什至不确定它所基于的假设是否仍然成立......

- 是否可以根据我的需要调整该算法？

- 或者我可以使用另一种同样有效的线性算法吗？

- 谁能提供伪代码或详细解释？

谢谢。

链接到我正在调查的子集和代码： Pisinger 的子集和算法的快速解决方案

（抱歉，如果措辞/格式/等不好。我还是 StackOverflow 的新手......）

在使用动态规划伪多项式时间算法解决分区问题后，我需要找到最佳子集。

更具体地说，我无法理解这个答案：https ://stackoverflow.com/a/890243/1317826

我无法理解如何从布尔表中构造最佳子集。

关于分区问题的维基百科文章也有：http ://en.wikipedia.org/wiki/Partition_problem

有人可以解释一下吗？

我正在尝试解决一个动态编程问题，部分问题涉及找到一组“p”数字的排列数，这些数字总和为一个数字“n”。p 个数集合中的每个数应介于 0 到 n 之间。

例如，如果 n = 4 和 p = 3，我有以下 12 个排列

我从这种 DP 方法开始。

我的基本情况是

（例如，p=3 处的 n(4,0) 为 3，即 {4,0,0},{0,4,0},0,0,4}

递归案例

（例如：n(1,2) = n(1,1) * n(0,2) 递归到 n(1,0) * n(0,1) * 2)

我不确定我是否朝着正确的方向前进，因为上述方法并没有让我得到正确的答案。请指导我正确的方向。

子集问题在 Wikipedia 中定义如下：

给定一组整数，是否存在总和为零的非空子集？例如，给定集合 { -7, -3, -2, 5, 8}，答案是肯定的，因为子集 { -3, -2, 5} 的总和为零。

或者

给定一组整数和一个整数 s，是否有任何非空子集和 s？

这个问题的蛮力解决方案是指数的（循环遍历 N 个数字的所有子集，并且对于每个子集，检查子集的总和是否为正确的数字），还有一些针对在指数时间内运行的蛮力的优化版本。

假设有一种算法可以在二次和多项式时间复杂度之间计算蛮力解决方案（上述问题的精确解决方案）

它如何被认为与 P=NP 问题、时间复杂度等有关？

假设存在算法，是否会改进子集和问题的最新技术？

（我不是这方面的专家，所以如果有些事情没有意义或不清楚，我会在力所能及的范围内为这个问题提供额外的输入:)）

给定：整数数组 K,M

问题：找到我们可以从给定数组的所有 K 个元素子集中获得的最大和，使得和小于值 M？

这个问题有可用的非动态编程解决方案吗？或者如果只有 dp[i][j][k] 只能解决这类问题！你能解释一下算法吗？

我有一个正整数数组 {a1, a2, ...., an}，我想找出满足以下条件的数组的所有可能子集：

其中 K 是一个正整数。我知道这个问题的解决方案是动态编程，但无法思考如何在这种情况下使用它。请帮忙。

PS：我并不完全需要所有子集，而是说形成所有子集的所有元素的乘积。

我有以下数学问题，我在应用程序中需要它，我想知道是否有一种有效的方法来找到最佳解决方案而不是近似值。

1. 我有一个正负值列表。
2. 这些值的总和在 (x, y) 范围内。
3. 我想知道我可以消除的最大值数，以便剩余值的总和保持在范围内。

例子：

消除 15 将使 SUM = 0，超出范围。消除了 5 个值。

而如果我从消除 15 开始，然后是 -10、-5、-2，我只能消除 4 个值。

我曾经写过一个算法，它简单地尝试了所有可能的组合，但是一旦你有 25 个或更多的值，它的性能就会迅速下降。对于 100-200 个值，我需要十分之一秒的结果。

目前，我在绝对基础上将值从小到大排序，然后逐个消除它们，直到总和不再在范围内。显然，这可能并不总是给出最佳解决方案。

如果这不是此类问题的正确位置，并且您可以参考另一个论坛，那也会有所帮助。

在 MathExchange 中交叉发布以引起更多响应。

==================================================== ===============================

当我意识到之前有人问过这个问题时，我正在 StackOverflow 中写我最初的问题。

原来我有所谓的子集和问题，所以我去了维基百科并找到了这部分。

但是我在理解维基百科中编写的伪代码时遇到了问题。

例如，我认为目标是找到可以匹配 S 的最接近的一组数字。

但这里 S 是一个列表。这个元素为 0 的 S 列表是什么？

到底是 if y + cs/N < z ≤ s什么？我什至如何用代码写出来？

我希望有人能帮我把它翻译成 php 代码。

至少我对此比较熟悉。它不必是完整的翻译。

只要答案让我足够理解这个近似算法，让我自己用 php 代码编写它，就可以了。