2

您有 2 个数组 a 和 b,每个数组包含 n 个数字。你有一个数字k。

[n] = 索引集 1...n

我们希望找到 [n] 的子集 S,使得 a 中 S 索引的元素总和至少为 k,并且 b 中 S 索引的元素总和尽可能小。

我什至找不到一个多项式时间算法。对于如何解决此问题的任何想法,我将不胜感激。

4

2 回答 2

0

你至少对多项式感兴趣,对吧?易于对集合的所有掩码进行指数迭代并检查两个条件(总和 >= k 并比较我们之前在 b 和现在的总和中所拥有的内容)

于 2012-07-31T17:55:38.867 回答
0

这个问题的一般解决方案是 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) <= Tsum(a[i] indexed by S) >= k

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

由于所提出问题的解决方案在有效 S 上最小化sum(b[i] indexed by S),在有效 Ssum(c[i] *not* indexed by S)上最大化,并且是背包问题的最优解。

于 2012-07-31T19:29:05.793 回答