選擇一個整數來最大化總和

如果我們給出了整數對(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

選擇一個整數來最大化總和

回答

相關問題