The 0/1 Knapsack problem is one of the most important Dynamic Programming interview questions.

You are given:

weights[]values[]
capacity

Goal:

Maximize total value without exceeding the capacity. 

Rule:

Each item can be picked at most once. 

This is why it is called:

0/1 Knapsack 

Example

weights = [1,3,4,5]values = [1,4,5,7]
capacity = 7

Output:

9 

Explanation:

Pick item with weight 3Pick item with weight 4
Total Value = 9

Key Observation

For every item:

Two choices exist:
Pick or Not Pick

Recurrence:

dp[i][w] = max(dp[i-1][w],values[i] + dp[i-1][w-weights[i]]) 

This is the famous:

Pick / Not Pick Pattern 

Approach 1 : Memoization

Explanation

Use recursion and store answers.

Steps:

1. Pick current item.
2. Skip current item.
3. Take maximum value.
4. Store results.
5. Reuse calculations.

Approach 2 : Tabulation

Explanation

Build a DP table.

State:

dp[i][w] = Maximum value using first i items and capacity w 

Transition:

Not Pick:
dp[i-1][w]

Pick:
values[i] + dp[i-1][w-weights[i]] 

Take maximum.

Dry Run

Input:

weights = [1,3,4,5]
values = [1,4,5,7]
capacity = 7 

Best Selection:

Weight 3 + Weight 4 = 7 

Value:

4 + 5 = 9 

Answer:

9 

Approach 3 : Space Optimized DP

Explanation

Instead of storing:

n × capacity 

Store only:

One DP array 

Traverse capacity from right to left.

This avoids reusing the same item twice.

Practice

MemoizationTime Complexity: O(n × capacity)
Space Complexity: O(n × capacity)

Tabulation
Time Complexity: O(n × capacity)
Space Complexity: O(n × capacity)

Space Optimized DP
Time Complexity: O(n × capacity)
Space Complexity: O(capacity)

For every item:Either pick it or skip it.