数组中具有最小总和的索引集的特定子集

您有2个数组a和b，每个数组包含n个数字。你有一个数字k。数组中具有最小总和的索引集的特定子集

[N] =索引设置为1 ...... n

我们想找到的子集S [n]的，使得元件的被S中一个索引的总和至少为K，并且总和在S中由S索引的元素的数量尽可能小。

我无法找到甚至多项式时间算法。我会很感激有关如何解决这个问题的任何想法。

2012-07-31 user36338

这是功课吗？你目前有什么方法？子集S不一定是连续的元素，对吗？ – hatchet 2012-07-31 16:41:23

以下类似的问题可能会给你一些想法：http://stackoverflow.com/questions/8099334/maximum-subset-sum-with-two-arrays http://stackoverflow.com/questions/443712/algorithm-to-找到子集中的两个整数集合，其和数匹配/ 443950＃443950 – hatchet 2012-07-31 16:50:38

这不是家庭作业。我正在读一个关于向玩家分配资源的问题，在特殊情况下降低到这个水平。我现在看到这是NP完全的。背包可以在多项式时间内解决到任何精度，我们也可以通过在目标值上进行二分搜索来减少背包。所以，我想这也可以在多项式时间内解决任何准确性，但我必须验证这一点。 – user36338 2012-08-01 08:09:58

该问题的一般解决方案是NP完全的，因为它包含背包问题。但是，与背包问题一样，您可以使用动态规划以建设性的方式（在“多项式时间”中）解决它。

要看到这一点：给定一个背包问题，背包大小T和对象大小c[i]，在你的问题，使得a[i]==b[i]==c[i]和k == sum(c[i]) - T描述构成一个问题。

然后，解决背包问题是一组指标在S不：

sum(c[i] *not* indexed by S) == sum(c[i]) - sum(a[i] indexed by S) 

T == sum(c[i]) - k

注意S满足背包约束sum(c[i] *not* indexed by S) <= T当且仅当问题约束sum(a[i] indexed by S) >= k成立。

sum(c[i] *not* indexed by S) == sum(c[i]) - sum(b[i] indexed by S)

自向提出问题的解决方案最小化sum(b[i] indexed by S)超过有效S，sum(c[i] *not* indexed by S)被最大化超过有效S，并且是背包问题的最佳解决方案。

来源

2012-07-31 19:29:05 comingstorm

你对至少多项式感兴趣吗？容易有指数迭代所有掩码的设置和检查两个条件（sum> = k并比较我们之前总结的b和现在）

来源

2012-07-31 17:55:38

数组中具有最小总和的索引集的特定子集

回答

相关问题