-1

これはインタビューの質問です：

4 人の男性 - それぞれ 1、3、7、10 分で橋を渡ることができます。一度に橋を渡ることができるのは 2 人だけです。彼らが橋を渡るのに何分かかりますか。

解決策を次のように手動で考えることができます: 10 と 7 が一緒になり、7 が目的地に到達するとすぐに「3」がホップインし、10 と 3 が一緒に完了します。1 は自然に進み、合計所要時間は 11 です。したがって、{10, 7} の後に {10, 3} が続き、その後に {1} が続きます。

これを一般的なアルゴリズムのコードに実装する方法を考えることができません。このアイデアを実際のコードに変換する方法を特定するのを手伝ってくれる人はいますか?

4

2 に答える 2

2

あなたが説明する問題はサブセット合計ではありません。

それでも、次のことができます。

order the array a by descending time
int time1 = 0;  // total time taken by the first lane
int time2 = 0;  // total time taken by the second lane
for i : 0..n
    if(time1 < time2)   // add the time to the most "available" lane
        time1 += a[i];
    else
        time2 += a[i];
    endif
endfor
return max(time1, time2);
于 2013-08-22T07:25:41.647 に答える