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 に答える