0

仕事の候補者のリストを入力として受け取ったので、受け取ったリストはすでに各自の給与の要件によってソートされており、大学からの給料でもあります（このパラメーターはソートされていません）。例：

ダニー13000$75.56

ダン9000$100

ボブ5000$98

このようなリストでは、両方の給与の合計が10000ドルを超えないように、より高い学年の2人の候補者を見つける必要があります（同じ学年の2人の候補者はなく、2組の学生はいないと推測できます。グレードの同じ合計（94 + 90 = 91 + 93））

O（n）の複雑さでそれらを見つける必要があります。

ソートアルゴリズム（最小値はn * log（n））を実行できないことを理解しているので、どうすればそれを実行できますか？

出来ますか ？

4

2 に答える 2

1

給与でソートされているため、2 つのポインターで開始します。i は開始点 (最低の売上) を指し、j は最高の売上を指します。売上高が制限を超えている間、j. ここで i を増やし、j を減らして制限を超えないようにします。i と j の最大グレードを追跡します。

于 2012-12-27T11:30:21.107 に答える
1

O(n)解決策（10,000という数字が固定されていると仮定）：

arr <- new empty array of size 10000
for each i from 1 to 10000:
   arr[i] = "most valuable" worker with salary up to i
best <- -infinity
for each i from 1 to 5000:
   best = max{ best, arr[i] + arr[10000-i]}
return best

アイデアは、配列を保持することです。各エントリには、最大でその給与を要求した「最良の」候補者が保持されます (これは最初のループで行われます)。

2 番目のループでは、実行可能なすべての可能性を検討し、最大値を見つけます。

最初のループの単純なアプローチはO(n)ひどい定数を使用していることに注意してください (各反復はO(n)であり、10,000 回実行されます)。arrただし、 DP を使用して、最低の給与から上に移動し、次のようにすることで構築できます。

arr[i] = max {arr[i-1], best worker with salary i}

DP ソリューションはO(n)、配列を 1 回だけトラバーサルします (または正式O(W+n)にWは最大給与はどこにありますか)。

また、これはナップザック問題のプライベート ケースであり、2 つの要素しか選択できません。

于 2012-12-27T11:22:24.320 に答える