2019会社の同僚とアルゴリズムの勉強会を少人数で始めました。最終的にはGoogleに転職する頭でアルゴリズムを考える力をつけるのが目的です。実際にやってみて一人で勉強していくよりも相談しながら解いていくほうが考えがより深まるような感じがあります。今回はナップサック問題を動的計画法で解くのを勉強しました。数年前に応用情報を受験したときの本番で出た問題でした。当時はナップサック問題を知らなかったので、なんとなく解いた記憶があります。超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか要は、効率よくナップサックに詰め込むために品物の組み合わせを求めよってことです。実際に出た問題はこちらです。午後問3)問題文が結構長いですが、要約すると下記のようなitemsの配列とcontainerSizeが渡されて、valueの最大値とその時のitemsの組み合わせを返す関数をつくるという感じです。4;サンプルを作りました。https://codepen.io/kwst/pen/wbrRMR?editors=1011作成した関数はこれです。実際に組み合わせを求めようとすれば総当たりで計算していくので、O(N^N)になるかな?動的計画法を用いているので、一度それまでの結果をキャッシュしておいて、計算を削減しています。試験の会場で実際に解いているときは、答えを出すことに必死でしたので結果をキャッシュして計算を削減してるんだなぁとか噛みしめる余裕もなかったです。一度考え直してみるとなるほどなぁという感じです。kwst.site.。