第2回：ナップサック問題を色々な方法で解いてみた【ブレインパッドの数理最適化ブログ】 - Platinum Data Blog by BrainPad

ブレインパッドの社員が「数理最適化技術」に関して連載するこの企画。 第2回は、当社のデータサイエンティストが、有名問題「ナップサック問題」の様々な解法を紹介しながら、実際に筆者が設定した問題例を解く過程を紹介しています。 こんにちは。アナリティクスサービス部の内池です。この記事では 【連載】ブレインパッドの数理最適化ブログ の第2弾として、最適化手法入門 (データサイエンス入門シリーズ) を読んで学んだことを活かし、現実の問題を様々な方法で解いていきたいと思います。 今回のテーマは組合せ最適化の有名問題であるナップサック問題です。ナップサック問題といえば「動的計画法」を思い浮かべる方が多いと思いますが、動的計画法だけでも様々なバリエーションがある他、動的計画法以外の効率的な解法も存在します。これらについて、実際に問題を解きながら追っていきましょう。 ナップサック問題とは 注意 様々な解法