algorithm - 数组中总和最小的索引集的特定子集

Question

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

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

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

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

Answer 1

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

Answer 2

这个问题的一般解决方案是 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)上最大化，并且是背包问题的最优解。