Loading...

プレビュー

全64ステップ中20ステップのみ表示

ログインして全て見る

0/1ナップサック問題

中級

0/1 Knapsack

限られたナップサックに何を入れるべき?

📊 計算量

区分	計算量
最良	O(n * W)
平均	O(n * W)
最悪	O(n * W)
空間	O(n * W)

🏷️ Tags

DP2Dテーブル最適化

📖 概念紹介

バックパックのスペースは限られていますが、入れたい物はたくさんあります。どう選べば価値の合計を最大にできますか？

1/64

Loading...

🎯状況説明

鞄に品物を入れて最大価値を得たい! • 鞄の容量: 7kg • 4個の品物: 🎸Guitar, 💻Laptop, ⛺Tent, 🏆Gold • 各品物は「入れる(1)」か「入れない(0)」のどちらか!

🔒

基礎学習

0/1ナップサック問題

定義

バックパックのスペースは限られていますが、入れたい物はたくさんあります。どう選べば価値の合計を最大にできますか？

主な特性

✓表の使用: 「もし容量が1なら？2なら？」と小さい問題から答えを出して表に記録します。
✓漸化式: 「入れるか、やめるか」の2つを比較するだけです。

時間計算量

最良

O(n * W)

平均

O(n * W)

最悪

O(n * W)

空間計算量

O(n * W)

0/1ナップサック問題 | AlgoNote