Overview
0/1 Knapsack: limited capacity bag mein max value items fit karo — DP ka classic problem.
Analogy
Jaise chhuti pe bag pack karo — weight limit hai, most valuable items daalo.
Step-by-step
- dp[i][w] = max value using first i items with capacity w
- Item i choose ya na choose — max dono ka
- dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi)
- Base case: dp[0][*] = dp[*][0] = 0
Visual
items: [(w=1,v=1),(w=3,v=4),(w=4,v=5),(w=5,v=7)]
capacity=7
Optimal: item 4 alone -> value=7
Common mistakes
- 0/1 vs unbounded knapsack confusion — 0/1 har item ek baar
- dp table iteration order — outer items, inner weights
- 2D se 1D space optimize karte time reverse iteration zaroori
Practice questions
- 0/1 knapsack implement karo
- Partition equal subset sum solve karo (knapsack variant)