【Python/アルゴリズム】数学の壁をぶち壊してナップザック問題を理解したい...!!
はじめに
こんにちは!数学嫌いですか!!!!????
数学は嫌いだけど論理的思考は好きなんですよね....
きっとこれを手にとっている皆さんなら嫌いでしょう。信じています。
今回はそこまで数学を嫌ってきた私が「数学的に難しい理論は抜きにして、実務で実装するイメージでナップザック問題を理解してみよう!」というコンセプトでPythonのコードを交えながら解説します。想定読者はコンピュータサイエンス専攻の学生や、アルゴリズムを学びたい方です。ナップザック問題自体を初めて知る人にもわかりやすいように進めますので、ぜひ最後まで読んでみてください!
1. ナップザック問題とは?
1. 問題の概要
ナップザック問題(Knapsack Problem)は、与えられた物品の中から一部を選択し、カバン(ナップザック)の容量を超えないように詰めて、その価値の合計を最大化するという有名な組合せ最適化問題です。
- 物品(アイテム):価値(value)と重さ(weight)がある
- ナップザック(カバン):許容量(容量 W)がある
- 目的:ナップザックに入れるアイテムを選び、価値の合計を最大化
たとえば、以下のようなアイテムがあるとします。
アイテム | 価値 (value) | 重さ (weight) |
---|---|---|
1 | 4 | 12 |
2 | 2 | 1 |
3 | 10 | 4 |
4 | 2 | 1 |
5 | 1 | 2 |
そしてナップザックの容量 ( W ) が 15 だとすると、どの組み合わせでアイテムを詰めれば価値の合計が最大化するのかを考えるわけです。
2. 数式による定式化
「数学は苦手」とは言いつつ、アルゴリズムとして理解するためにも一度定式化に触れてみましょう。0-1 ナップザック問題(アイテムを入れるか入れないかの二択)の定式化は次のとおりです。
-
:アイテムv_i の価値i -
:アイテムw_i の重さi -
:アイテムx_i を選ぶなら 1、選ばないなら 0i
いや書いてみたけどなんだよまじで。
ただ「数学アレルギー」がある方、ここで萎縮しなくて大丈夫。こうした式は最適化したい指標(ここでは合計価値)を最大化するために守るべき制約(カバンの容量)を示したものだとざっくり認識しておく程度でもOKです。
2. 数学が苦手でも理解できるポイント
1. まずは「詰める・詰めない」の組み合わせを考える
ナップザック問題は**「全探索(総当たり)」をイメージすると分かりやすいです。アイテムが 5 つあったら、各アイテムを「入れる」「入れない」の二択で、組み合わせは (2^5 = 32) 通り。これは小規模**なら試せますが、アイテム数が大きくなると、とんでもない数になってしまい現実的ではありません(計算量が爆発的に増えます)。
2. 動的計画法(DP)で賢く探索を進める
一般的には、動的計画法 (DP: Dynamic Programming) を使って、より効率的に計算する手法が知られています。
**「何個目までのアイテム」と「使える容量」に応じて最適な値を順次求めていく」**のが基本の流れです。
- DP テーブルという表を用意して、行にアイテム番号、列に容量を設定。
- 1 行目(アイテム1から)から順番に「入れる」「入れない」の結果を更新していく。
ここでは、あくまで「テーブルのイメージ図」をmermaidのフローチャートで表現してみましょう。「アイテム × 容量」それぞれに対応するセルがあるイメージをフローチャートでざっくり可視化してみます。
上記は**「行 × 列」の概念を無理やりフローチャートで表現しただけですが、実際のDP テーブル**のイメージは下記のようになります。
容量0 | 容量1 | 容量2 | ... | 容量W | |
---|---|---|---|---|---|
アイテム1 | DP[1][0] | DP[1][1] | DP[1][2] | ... | DP[1][W] |
アイテム2 | DP[2][0] | DP[2][1] | DP[2][2] | ... | DP[2][W] |
アイテム3 | DP[3][0] | DP[3][1] | DP[3][2] | ... | DP[3][W] |
... | ... | ... | ... | ... | ... |
アイテムn | DP[n][0] | DP[n][1] | DP[n][2] | ... | DP[n][W] |
各セルに「そこまでのアイテム + そのときの容量で達成できる最大価値」が入っていくわけです。
「数式や理論というよりは、この表(= DP テーブル)の更新手順が実装に直結する」という感覚で理解できれば OK です。次の章では、この DP テーブルを実際に Python でどう構築しながら計算するかを見ていきましょう。ぜひ手を動かしてみてください。
3. Pythonによる実装例
ナップザック問題を解くためのPythonコードを、DPベースで書いた場合の主要部分を紹介します。ここでは記事が長くなるため、コードの全量は省略し、参考資料として外部で確認できるようにします。今回はポイントだけ解説します!
1. ポイント解説
-
アイテム情報の準備
items = [ {"value": 4, "weight": 12}, {"value": 2, "weight": 1}, {"value": 10, "weight": 4}, {"value": 2, "weight": 1}, {"value": 1, "weight": 2} ] W = 15 # ナップザックの容量
-
DPテーブルの初期化
dp = [[0] * (W+1) for _ in range(len(items)+1)]
-
dp[i][w]
は「i番目までのアイテムを考慮した時の容量 w における最大価値」を表します。
-
-
テーブル更新のループ
for i in range(1, len(items)+1): value = items[i-1]["value"] weight = items[i-1]["weight"] for w in range(1, W+1): if weight <= w: # 入れるケースと入れないケース dp[i][w] = max( dp[i-1][w], # 入れない場合 dp[i-1][w-weight] + value # 入れる場合 ) else: dp[i][w] = dp[i-1][w]
- もし今のアイテムの重さが容量 w に収まるなら → 入れる/入れない のどちらがより価値が高いかを比較
- 収まらないなら → 入れられないので、前の状態をそのまま継承
-
最終的な解
# dp[len(items)][W] が答え max_value = dp[len(items)][W] print("最大価値:", max_value)
- DPテーブルの最終行・最終列の値が、求める最大価値になります。
2. 実装結果イメージ
実際に上記のロジックを動かすと、アイテムの組み合わせ次第ですが、以下のような出力結果が得られます。
最大価値: 14
この例では、価値の合計が 14 となる組み合わせ(例:アイテム2, アイテム3, アイテム4, アイテム5)を選んだときが最適だった、というわけです。
4. 出力例から分かること
1. 組み合わせの最大価値が瞬時に分かる
DPを使うと、総当たりに比べて格段に効率良く最適解を導くことができます。アイテム数や容量が増えても、DPテーブルの大きさに応じた計算量で済むため「計算量が爆発する」リスクが小さくなるのが嬉しいところです。
2. 「数学」は道具の1つ、実装で補完できる
ナップザック問題を最初に学ぶと「こんな数式みても分からん!」という気持ちになるかもしれません。死ぬほどわかります。でも実際には、表(DPテーブル)の更新手順と実装に落とし込む流れが分かると、数式のイメージがつかめたりします。
5. まとめと今後の学び方
- ナップザック問題は「入れる or 入れない」の組合せによって価値最大化を狙う問題
- 数式が苦手でも、「DPテーブルの更新」という流れで実装に落とし込める
- Pythonで書いてみるとHandsOnで理解できる
私は数学は苦手ですが、ロジック構築の力を応用して、実装を通じて理解できることが多いと感じています。大学の数学でつまづいた方も、まずはサンプルコードを手を動かして試すところからぜひ始めてみてください!
もし何か質問や指摘などありましたら、コメント等で教えていただけると幸いです。
これからも「数学苦手、だって俺高卒だし。」を言い訳にせず、実装でどんどん理解を深めていきたいと思います。最後まで読んでいただきありがとうございました!
Discussion