0

如果给定整数对(a1,b1),(a2,b2),(a3,b3),..(an,bn)并且存在最大和值 =X那么我们如何选择给定的对，使得所选对中的第一个条目（即 a1、a2、..ap）的总和为maximum but <= X？例如，如果给定的对是(43,9),(57,12),(13,4)并且最大和是，71那么我们可以选择的对是(57,12)并且(13,4)给出最大和 <=71(X) 为 70 。我最初的方法是根据第一个条目值按降序对对进行排序，然后可能是 O(n^2) 算法..但我不确定这一点，对于大量数据来说它也可能太慢..所以有什么有效的方法吗？谢谢。

4

1 回答 1

1

听起来这可以通过修改0-1 背包问题来实现。

于 2012-08-23T02:38:11.573 回答