dynamic-programming - 同时子集和

Question

我正在处理一个问题，它是子集和问题的变体，我希望额外的约束可以比经典的子集和问题更容易解决。我已经搜索了这个约束的问题，但是我无法在 StackOverflow 上或通过其他地方的谷歌搜索找到一个具有适当算法的好例子。

问题：

假设您有两个正数列表 A1,A2,A3... 和 B1,B2,B3... 具有相同数量的元素 N。有两个和 Sa 和 Sb。问题是找到同时集 Q 其中 |sum (A{Q}) - Sa| <= epsilon 和 |sum (B{Q}) - Sb| <= ε。因此，如果 Q 是 {1, 5, 7}，则 A1 + A5 + A7 - Sa <= epsilon 和 B1 + B5 + B7 - Sb <= epsilon。Epsilon 是一个任意小的正常数。

现在，我可以将其作为两个完全独立的子集和问题来解决，但删除同时性约束会导致错误解决方案的可能性（其中 Qa ！= Qb）。我还怀疑附加约束应该比两个 NP 完全问题更容易解决这个问题。我想解决两个数字列表中包含 18 个以上元素的实例，并且大多数子集和算法在这些元素的情况下运行时间很长。我已经研究了伪多项式运行时动态规划算法，但这有以下问题：a）速度依赖于数字列表的短位深度（这不一定适用于我的实例）和 b）它确实不考虑同时性约束。

关于如何使用同时性约束来减少运行时间的任何建议？有没有我可以用来考虑这个约束的动态编程方法？

标签： dynamic-programmingsubset-sum

Answer 1

如果我正确理解了您对问题的描述（我对为什么您在“sum (A{Q}) - Sa”和“sum (B{Q}) - Sb”周围有距离符号感到困惑，它不会似乎符合其余的解释），那么它在NP中。

您可以通过从子集总和 (SUB) 减少到同时子集总和 (SIMSUB) 来看到这一点。如果您有一个由集合 X = {x1,x2,...,xn} 和一个名为 t 的目标组成的 SUB 问题，并且您有一个算法可以在给定两个集合 A = {a1,a2,... 时解决 SIMSUB ,an} 和 B = {b1,b2,...,bn}，两个整数 Sa 和 Sb 以及 epsilon 的值，然后我们可以像这样求解 SUB：令 A = X 并令 B 是长度为 n 的集合，包括只有 0 的。设置 Sa = t、Sb = 0 和 epsilon = 0。您现在可以在这个问题上运行 SIMSUB 算法并得到您的 SUB 问题的解决方案。这表明 SUBSIM 与 SUB 一样难，因此在 NP 中。