2021-プレゼント2-解説
- 考案国：ドイツ
- 正解
- 説明
- 同じプレゼントを欲しいビーバーが2匹いますので、全員に一番好きなプレゼントを渡すことはできません。まず、一番好きなプレゼントが重なっていない3匹については、そのプレゼントを渡すことにしましょう。
次に、一番好きなプレゼントが重なっている2匹について考えます。2匹を見ると、二番目に好きなプレゼントは、1匹はまだ渡されていませんが、もう1匹はすでに他のビーバーに渡されていることがわかります。
そこで、「2番目に好きなプレゼントが他のビーバーに渡されている」ビーバーに一番好きなプレゼントを渡し、「2番目に好きなプレゼントがまだ渡されていない」ビーバーに二番目に好きなプレゼントを渡すことで、すべてのビーバーが一番好きなプレゼントか二番目に好きなプレゼントを受け取ることができました。
- 同じプレゼントを欲しいビーバーが2匹いますので、全員に一番好きなプレゼントを渡すことはできません。まず、一番好きなプレゼントが重なっていない3匹については、そのプレゼントを渡すことにしましょう。
- 実際のコンピュータでは
- この問題では、ビーバーたちは一番目と二番目の希望を言いました。他のプレゼントは、すべて三番目と考えることができます。
- できるだけ一番目の希望をかなえるか、できるだけ二番目の希望をかなえる組み合わせが他にないとき、その組み合わせは最適になります。
- コンピュータ科学では、このような組み合わせ問題を「最大マッチング問題」と呼んでいます。組み合わせ問題にはいろいろなものがありますが、中には「安定した結婚問題」というものがあります。面白そうですよね。ぜひコンピュータ科学を学んでみてください！
注があるものを除き, このサイトの内容物は
