Golangでの0-1ナップサック問題の実装 - Qiita

Goで0-1ナップサック問題を解く ナップサック？ナップザック？どちらも見かけるような気がします． 英語ではKnapsack（nˈæpsæk）なのでサックなような気がします． 目的・理由 最近仕事でナップサック問題で解決出来る問題と遭遇した． 仕事全体の中では非常に小さい問題ではあったがアルゴリズムが直接役に立ったことを大変嬉しく思っており，記念に初めて記事を書く． Goで書くのはGoを書きたいというささやかで非常に素朴なアピールである． 想定読者 未来のわたし ナップサック問題とは ナップサック問題には制約によって様々な解法パターンがあるが今回の対象となるのは，もっともオーソドックスな0-1ナップサック問題と呼ばれるケース． 以下に簡単な問題設定を記載する． 容量$W$のナップサック1つと，$N$個の荷物$a_i (1\le i\le N)$がある． 各荷物には重さ$w_i$と価値$v_