Loading...

Preview

Showing 20 of 64 steps

Login to see all

0/1 Knapsack

Medium

0/1 Knapsack

What should you pack to maximize value?

📊 Complexity

Type	Value
Best	O(n * W)
Average	O(n * W)
Worst	O(n * W)
Space	O(n * W)

🏷️ Tags

DP2D TableOptimization

📖 Introduction

Limited backpack space, many items to pack. How do we choose items to maximize total value?

1/64

Loading...

🎯Problem Setup

Pack the bag to maximize value! • Bag capacity: 7kg • 4 items: 🎸Guitar, 💻Laptop, ⛺Tent, 🏆Gold • Each item: Take(1) or Skip(0) - no splitting!

🔒

Basics

0/1 Knapsack

Definition

Limited backpack space, many items to pack. How do we choose items to maximize total value?

Key Characteristics

✓Use Table: Solve for small capacities (1, 2, ...) and record answers.
✓Recurrence: Compare "Take" vs "Skip".

Time Complexity

Best

O(n * W)

Average

O(n * W)

Worst

O(n * W)

Space Complexity

O(n * W)

0/1 Knapsack | AlgoNote