動的計画法Intermediate

0/1ナップサック問題

与えられた重さと価値を持つアイテムを選択し、重量制限内で総価値を最大化する古典的な動的計画法の問題です。各アイテムは一度だけ取ることができます（0/1）。リソース配分、ポートフォリオ最適化、貨物積載に応用されます。

#dynamic-programming#optimization#combinatorial#np-complete

Complexity Analysis

Time (Average)

O(n × W)

Expected case performance

Space

O(n × W)

Memory requirements

Time (Best)

O(n × W)

Best case performance

Time (Worst)

O(n × W)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 16•Section 16.2

Items (weight:value, comma-separated)

Capacity (1-100)

Example Problems:

How it works

• 0/1 Knapsack: maximize value within capacity limit
• Dynamic programming approach
• O(n × W) time, O(n × W) space complexity
• Each item can be taken once or not at all
• Formula: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in 動的計画法

行列連鎖乗算

Advanced

スカラー乗算の数を最小化するために行列の連鎖を括弧でくくる最適な方法を見つけます。CLRSの第15章の古典的な動的計画法の問題です。

O(n³)

O(n²)

dynamic-programmingoptimization

Start Learning

フィボナッチ数列（動的計画法）

Beginner

動的計画法を使用して冗長な計算を避けながらフィボナッチ数を効率的に計算します。メモ化の力を示し、指数時間の再帰的解を線形時間アルゴリズムに変換します。動的計画法の概念への古典的な入門です。

O(n)

dynamic-programmingmemoization

Start Learning

最長共通部分列（LCS）

Intermediate

2つの列に同じ順序で存在する最長の部分列を見つけます。動的計画法を使用して解テーブルを構築します。DNA配列アライメント、ファイル差分ツール（diff）、盗作検出などの応用があります。

O(m × n)

dynamic-programmingstrings

Start Learning

Back to 動的計画法