您有 2 个数组 a 和 b,每个数组包含 n 个数字。你有一个数字k。
[n] = 索引集 1...n
我们希望找到 [n] 的子集 S,使得 a 中 S 索引的元素总和至少为 k,并且 b 中 S 索引的元素总和尽可能小。
我什至找不到一个多项式时间算法。对于如何解决此问题的任何想法,我将不胜感激。
您有 2 个数组 a 和 b,每个数组包含 n 个数字。你有一个数字k。
[n] = 索引集 1...n
我们希望找到 [n] 的子集 S,使得 a 中 S 索引的元素总和至少为 k,并且 b 中 S 索引的元素总和尽可能小。
我什至找不到一个多项式时间算法。对于如何解决此问题的任何想法,我将不胜感激。
你至少对多项式感兴趣,对吧?易于对集合的所有掩码进行指数迭代并检查两个条件(总和 >= k 并比较我们之前在 b 和现在的总和中所拥有的内容)
这个问题的一般解决方案是 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)
由于所提出问题的解决方案在有效 S 上最小化sum(b[i] indexed by S)
,在有效 Ssum(c[i] *not* indexed by S)
上最大化,并且是背包问题的最优解。