2021-働く2匹のビーバー-解説
- 考案国:リトアニア
- 正解
- 正解は23時間です。
- 説明
- 作業にかかる時間を合計すると46時間になります。2人で作業しますので、最短の時間は23時間より短くなることはありません。
- 作業の分担は、いくつかの正解が考えられます。
- 正解例(1)
ビーバー1: A(2)、C(5)、E(10)、H(6)
ビーバー2: B(3)、D(7)、F(9)、G(4) - 正解例(2)
ビーバー1: A(2)、B(3)、C(5)、F(9)、G(4)
ビーバー2: D(7)、E(10)、H(6)
- 正解例(1)
- 実際のコンピュータでは
- この問題では、「取り組める作業のうち一番時間がかかる作業を行う」という作戦で進めると、作業の空き時間ができてしまい、23時間で終わる作業が32時間かかってしまうという例を見ました。
- この問題では、この作戦は時間がかかってしまいましたが、他の問題ではうまくいくかもしれません。作業の最短時間を求めるアルゴリズムを考えることは簡単ではありません。確実なのはすべての作業の組み合わせを試してみることですが、作業が多いと計算だけで時間がかかってしまいます。