インタラクティブPythonラボ

0/1 Knapsack DP

プレイグラウンドはロード時に自動実行されます。コードを実行をクリックして自分のPythonをトレースしましょう — 各ステップがライブアニメーション。

説明·行ごと

リプレイ·ステップごと

チャレンジ·ガイド付きプロンプト

XP·...

データフローパイプライン

mastery トラック

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

説明

Line 1

knapsack(weights=[2,3,4,5], values=[3,4,5,6], capacity=8) called.

なぜこのアプローチ？

We have 4 items with given weights and values, and a knapsack capacity of 8. The goal is to find the maximum total value without exceeding the weight limit.

Structured Explanation

Overview

ナップサック問題: 最大重さWのバッグに、重さと価値を持つアイテムを入れて価値を最大化する。

Analogy

スーツケースに収まるだけの旅行グッズを詰めて価値を最大化する旅行者のようなもの。

Step-by-step

dp[i][w] = 最初のiアイテムで重さw以下の最大価値
空間最適化: 1Dの dp[w]で実装
各アイテムで逆方向に更新(0/1の場合)
最終値はdp[W]

Visual

items=[(2kg,3¥),(3kg,4¥),(4kg,5¥)] W=5 dp[5]=max(dp[3]+4, dp[5]) 最終dp: [0,0,3,4,4,7]

Common mistakes

0/1ナップサックで内ループを逆順にしない(重複)
分割ナップサックとの混同

Practice questions

0/1ナップサックを2Dと1Dで実装
ターゲット合計(重みのみ)問題に変形

Time

O(nW)

Space

O(W)

複雑度

時間

O(n × W)

空間

O(n × W)

複雑度概要

O(1)

O(log n)

O(n)

O(n log n)

O(n²)時間空間

n = 8範囲 1-20

N = 8 のとき

複雑度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

チャレンジ

0/1ナップサック問題を解きましょう: items=[(2,6),(2,10),(3,12)], capacity=5。DPテーブルを行ごとに構築。

ヒント

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])。

コードスタジオ

0/1 Knapsack DP

Monaco準備完了

Python準備完了

lesson.pyline 1

Loading editor...

出力コンソール

1 lines

❯ 10

実世界の応用例

1

Cargo shipment payload optimization

2

Investment maximum yield tracking

3

Micro-service CPU load balancing

Comments

Loading comments...