选择集合的子集使得子集满足全局约束条件

我们有一组项目I = {i_1，i_2，...，i_n}。这些项目中的每一项都具有我们所称的p值，这是一些实数。我们想选择I的一个子集，称为I'，其大小为m（对于某些具有1 < = m的< = m），使得I'中的项的值的平均值落入某个指定的范围内范围，[p_l，p_u]。（例如，我们可能需要的平均值在0.70和0.74之间。）此外，我们希望有效地完成此操作。选择集合的子集使得子集满足全局约束条件

我们希望在O（n）时间内做到这一点，但任何多项式时间算法都足够好。我们当然不想尝试每个可能的大小为m的I子集，然后检查它是否满足平均p值约束。

最后，我们将重复这样做，我们希望选择的子集在所有可能的子集上均匀随机分布。

有没有办法做到这一点？

来源

2010-08-24 Paul Reiners

对此，多项式时间算法似乎不太可能。这个问题可能相当于一般的*约束子集选择问题*，这是NP。如果您的输入值紧密聚集在某个数据透视点附近，并且具有正态分布，则可以使用回溯算法来选择符合要求的子集。但是，确保您对l的所有成员进行统一的随机分配将是具有挑战性的。你可能会有更好的运气在[mathoverflow.com]（http://www.mathoverflow.com）上寻求帮助。 – LBushkin 2010-08-24 16:41:27

感谢您的评论。我倾向于认为问题也是棘手的。我可能会问mathoverflow.com，但到目前为止，我发现堆栈溢出是更有帮助，即使这样的理论问题。 – 2010-08-24 17:15:12

如果您有一个子集及其总和，如果您将总和按| subset + 1 |/| subset |进行缩放，则您添加的每个新元素都会对总和做出线性贡献。这似乎与子集和问题（NP-complete）非常相似，其目标是找到所有总和为0的子集，尽管这里我们希望总和接近0.例如，如果你有一个大的设置一个元素大致在可接受的p范围内的位置，如果您粗略地假设该元素无关紧要，则突然实际上是相等的......假设您有大量的正负p值，并且问题不是由对手构建的。如果是这种情况，您可以使用http://en.wikipedia.org/wiki/Subset_sum_problem给出的两个近似解决方案之一，使相等性为“模糊”，然后仅在该“集合”上使用0.7“0.”0.74的“保留”元素。

当然，您可以从您的解决方案中剔除的效率是难以置信的，这取决于生成p值的方式（“分布”）。

来源

2011-05-06 01:23:51 ninjagecko

选择集合的子集使得子集满足全局约束条件

回答

相关问题