2014-貨物船-解説
- 正解
- １つの船に「120 90 90」の組合せで樽をのせ，もう1つの船に「130 100 60」の組合せで樽をのせると，2隻の船に積む樽の重さの合計が最大になります。
- 非対話型問題では「「100 130 60」と「120 90 90」」が正解です。
- 非対話型の選択肢を検討すると次のようのになります。
Lisa1の船 Lisa2の船 合計 220 60 280kg 130 120 90 340kg 重量オーバー 130 90 60 280kg 120 100 90 310kg 重量オーバー 120 90 90 300kg 220 60 280kg 合計580kg 100 130 60 290kg 120 90 90 300kg 合計590kg（正解）
- 非対話型の選択肢を検討すると次のようのになります。
- 解説
- さまざまな組み合わせの中から「制限の中で最大の荷物を載せる」という最適な組み合わせを見つけ出す問題です。
- 数がそれほど多くないもの同士の組み合わせでも，組合せ方は膨大になることがあります。そのため，コンピュータは高速に計算などを行えますが，すべての場合を調べてると時間がかかってしまいいつまでも処理が終わらないことがあります。
- 現在も効率良く最適解を求めるアルゴリズムの研究が続けられています。
- 出題国: この問題はドイツで作成されました。
注があるものを除き, このサイトの内容物は
