The 0/1 Knapsack Problem

The Knapsack Problem is the classic DP challenge. Given a set of items with weights and values, find the maximum value you can carry in a knapsack with limited capacity. Each item can either be taken (1) or left behind (0)—hence 0/1.

1. The DP Table Logic

We build a 2D table where dp[i][w] represents the maximum value using the first 'i' items and a knapsack capacity of 'w'.

• If the current item's weight > capacity: dp[i][w] = dp[i-1][w] (Don't take it).
• Else: dp[i][w] = Max(value + dp[i-1][w - weight], dp[i-1][w]) (Choose between taking it or skipping it).

2. Real-world Usecase

This isn't just about bags. It is used in Portfolio Optimization (which stocks to buy given a dollar budget), Video Encoding (which chunks of data to prioritize in a limited bandwidth), and Resource Allocation in cloud computing.

4. Interview Mastery

Q: "Can you solve the Knapsack problem with a Greedy approach?"

Architect Answer: "No, not the 0/1 version. The 0/1 Knapsack problem does not have the 'Greedy Choice' property. Picking the most valuable item per kg first might block you from picking two slightly less valuable items that together are worth more. Greedy ONLY works for the **Fractional Knapsack** problem where you can cut items (like liquid or gold dust). For 0/1 discrete items, you must use Dynamic Programming."