选择一个整数来最大化总和

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

来源

2012-08-23 pranay

我很困惑，如何才能最大总和同时是X和<= X（除非它只是X，在这种情况下，为什么有<？）。此外，这对＃号码如何适应？我想你可能会丢失或误解的问题的一部分。（编辑）OK，我想我明白了，你都获得了最高金额（X），所以必须选择是<= X） – user439407

我指的总和对的第一项必须是最大的但同时 71 – pranay

我认为'pranay'it是动态规划问题。在动态编程中寻找最大总和问题，这可能会对你有所帮助。但仍usuaully在这种特殊情况下，也将给予为O（n^2），但我认为我们可以通过这样的事情在O（n）的做到这一点：首先只考虑一对好喜欢43的第一部分，57然后类似于DP的加权区间调度问题，即通过如下方式获得概率的解：“或者第i个值将在解决方案中，或者它不会出现递归设计，因此解决方案要么是第i个成员，要么是从第i-1个成员' –

听起来这可能与0-1 Knapsack问题的修改来实现。

来源

2012-08-23 02:38:11 smang

谢谢..still总体复杂性将是O（n^2）我猜。 – pranay

我相信这将是O（NX），这可能是为O（n^2）若n == X – smang

的复杂性也将取决于整数n的值，（100,2）（201,2）（350,7），X = 95，使用备忘录递归版本可以做很少的工作。 – Xantix

选择一个整数来最大化总和

回答

相关问题