Overview
Knapsack problem: W capacity wale bag mein weights aur values wale items rakhkar maximum value nikalo.
Analogy
Jaise traveler limited weight travel bag mein most valuable items rakhta hai.
Step-by-step
- dp[i][w]=first i items jo w weight exceed nahi karte ka maximum value
- Space optimize: 1D dp[w] use karo
- Har item reverse order mein update karo (0/1 case)
- Answer dp[W] hai
Visual
items=[(2kg,3rs),(3kg,4rs),(4kg,5rs)] W=5
dp[5]=max(dp[3]+4, dp[5])
Final dp: [0,0,3,4,4,7]
Common mistakes
- 0/1 knapsack mein inner loop reverse nahi karna (duplicate selection)
- 0/1 aur fractional knapsack ka confusion
Practice questions
- 2D aur 1D dono mein 0/1 knapsack implement karo
- Target sum (sirf weights) problem mein convert karo