ナップサック問題(0/1)ビジュアライザー

0/1ナップサック問題を動的計画法(dynamic programming)でアニメーション表示 — DPテーブルを1マスずつ埋めながら、依存関係にあるセルをハイライトし、ステップ実行にも対応。ブラウザ上でそのまま動作します。

無料登録不要クライアントサイドプライバシーに配慮 Updated 6月 11, 2026

速度

疑似コード

Press Run to animate the algorithm.

使い方

1 Runを押すと、動的計画法のテーブルが1マスずつ埋まっていきます。
2 各行が1つの品物、各列が0からWまでの容量を表します。
3 各セルは、その品物を「取らない」場合(上のセル)と「取る」場合の値のうち、大きい方になります。
4 右下隅のセルが達成可能な最良の値です。Shuffleを押すと新しい品物セットが生成されます。

このツールを使う理由

0/1ナップサック問題を、総当たり(brute force)ではなく動的計画法で解く様子を確認できます。
各セルが依存する2つのセルからどのように構築されるかを観察できます。
総当たりの指数関数的な計算量に対し、O(n·W)の実行時間がどれほど効率的かを理解できます。
すべての処理はお使いのブラウザ内で完結します。登録不要、アップロードも不要です。

よくある質問

0/1ナップサック問題とは何ですか?

重さと価値を持つ複数の品物と、容量Wの制約が与えられたとき、各品物を「取る」か「取らない」かのみを選び(部分的に取ることは不可)、総重量がWを超えない範囲で価値の合計を最大化する組み合わせを求める問題です。

DPテーブルはどのように動作しますか?

dp[i][w]は、最初のi個の品物と容量wを使った場合の最良の価値です。各セルはmax(その品物を取らない場合 = dp[i-1][w]、取る場合 = dp[i-1][w-wi] + vi)で求められます。

計算量はどれくらいですか?

時間計算量はO(n·W)、空間計算量もO(n·W)です(O(W)まで削減可能)。これは擬多項式時間(pseudo-polynomial)と呼ばれ、Wが小さいほど効率的です。

なぜ「0/1」ナップサックと呼ばれるのですか?

各品物は丸ごと取る(1)か、まったく取らない(0)かのどちらかであり、一部だけ取ることはできません。これは、貪欲法(greedy)で解ける分数ナップサック問題(fractional knapsack)とは異なる点です。