ナップサック問題

数学の具体的な問題にPythonを使って、数学もPythonも同時に学んでしまいましょう。今回はPythonを使った確率・統計の問題として、ナップサック問題をみてみたいと思います。重量と価値の決まった品物をナップサックに詰める問題ですが、ナップサックには重量制限があり、制限を満たすなかで詰め込んだ品物の価値を最大化するのはどのような組み合わせか？という問題で、実用上も面白い問題です。ここでは重量に制限があるとしましたが、容量と読み替えても同じですし、あるいは問題をより複雑にするためには、重量と容量の両方に制限を設けて考察することもできるでしょう。今回は問題を簡単にするために重量のみについて制限…

はじめに 動的計画法 ナップサック問題 例題 考え方 実装例 おわりに 参考 はじめに こんにちは．talosです．今回はナップサック問題を例題に，動的計画法を説明します．競技プログラミングとかでもよく使われるので，これから挑戦しようという人は必見です． 動的計画法 動的計画法（DP：Dynamic Programming）は問題を部分問題に分割し，それらを解くことで最終的な解を求める方法です．似たような方法に分割統治法がありますが，これとの違いは部分問題を解いた結果を保存しておくことです．これによって，分割統治法でよくある同じ部分問題を何度も解いてしまうということを避けることができます．言葉…