DYNAMIC PROGRAMMING – 0/1 KNAPSACK

Complete Exam-Ready Notes + Solved Examples + C Code + Diagrams
(You will get full 15–20 marks in any DP Knapsack question!)

1. PROBLEM STATEMENT (Write First – 2 Marks)

Given:
- n items
- Each item has weight wᵢ and profit/value vᵢ
- Knapsack capacity = W

Goal: Maximize total profit without exceeding weight W
Constraint: Each item can be taken 0 or 1 time only (0/1 property)

2. RECURRENCE RELATION (Most Important – 5 Marks)

DP[i][w] = maximum profit using first i items with capacity w

DP[i][w] = DP[i-1][w]                                    → don’t take item i
           max( DP[i-1][w],   vᵢ + DP[i-1][w - wᵢ] )     → take item i (if w ≥ wᵢ)

Base cases:
DP[0][w] = 0 (no items)
DP[i][0] = 0 (capacity 0)

3. DP TABLE FORMAT (Draw This – 8 Marks Guaranteed!)

Classic Exam Question
n = 4, W = 8
Items: (w₁=2, v₁=12), (w₂=1, v₂=10), (w₃=3, v₃=20), (w₄=2, v₄=15)

Capacity →  0  1  2  3  4  5  6  7  8
Items ↓
0 (none)     0  0  0  0  0  0  0  0  0
1 (2,12)     0  0 12 12 12 12 12 12 12
2 (1,10)     0 10 12 22 22 22 22 22 22
3 (3,20)     0 10 12 22 30 30 32 42 42
4 (2,15)     0 10 15 25 30 37 40 42 57  ← Final Answer = 57

Optimal Solution: Take items 1, 2, 4 → weights 2+1+2=5 ≤8, profit 12+10+15=37? Wait, table says 57!

Correct items from backtracking:
DP[4][8] = 57 → came from v₄ + DP[3][6] = 15 + 42 = 57 → took item 4
DP[3][6] = 42 → came from v₃ + DP[2][3] = 20 + 22 = 42 → took item 3
DP[2][3] = 22 → came from v₂ + DP[1][2] = 10 + 12 = 22 → took item 2
DP[1][2] = 12 → took item 1

Final selected: Items 1,2,3,4 → weights 2+1+3+2=8, profit 12+10+20+15 = 57

4. COMPLETE DP TABLE WITH STEP-BY-STEP FILLING

w\i | 0  1  2  3  4  5  6  7  8
----+-------------------------
0   | 0  0  0  0  0  0  0  0  0
1   | 0  0 12 12 12 12 12 12 12   ← max(0, 12 + DP[0][w-2])
2   | 0 10 12 22 22 22 22 22 22   ← at w=2: max(12, 10+DP[1][1]=10+0)=12? Wait 22!
                                 Actually: max(DP[1][2]=12, 10 + DP[1][1]=10+0)=12 → wrong!
                                 Correct: at w=3: max(DP[1][3]=12, 10 + DP[1][2]=10+12=22) → 22
3   | 0 10 12 22 30 30 32 42 42   ← at w=6: max(22, 20 + DP[2][3]=20+22=42)
4   | 0 10 15 25 30 37 40 42 57   ← at w=8: max(42, 15 + DP[3][6]=15+42=57)

5. C CODE (Full Working – Practical Exam)

#include<stdio.h>
int max(int a, int b) { return (a>b)?a:b; }

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];

    for(int i=0; i<=n; i++) {
        for(int w=0; w<=W; w++) {
            if(i==0 || w==0)
                dp[i][w] = 0;
            else if(wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

int main() {
    int val[] = {12, 10, 20, 15};
    int wt[]  = {2,  1,  3,  2};
    int W = 8;
    int n = 4;
    printf("Maximum Profit = %d\n", knapsack(W, wt, val, n));
    return 0;
}
// Output: Maximum Profit = 57

6. SPACE-OPTIMIZED VERSION (1D Array – Advanced)

int knapsack(int W, int wt[], int val[], int n) {
    int dp[W+1];
    for(int i=0; i<=W; i++) dp[i]=0;

    for(int i=0; i<n; i++) {
        for(int w=W; w>=wt[i]; w--) {  // reverse loop!
            dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}

7. MOST ASKED EXAM QUESTIONS & ANSWERS

Q1 (15 Marks): Solve 0/1 Knapsack
Items: (w,v) = (1,1), (2,6), (5,18), (6,22), (7,28)
Capacity W = 11
→ Draw full 6×12 table → Answer = 40 (items 2,3,5)

Q2 (10 Marks): Why Greedy fails in 0/1 Knapsack?
→ Example: W=10
Item A: w=6, v=30
Item B: w=5, v=20
Item C: w=5, v=20
Greedy by v/w picks A (5) → total 30
DP picks B+C → total 40

Q3 (8 Marks): Time & Space Complexity
→ Time: O(nW)
→ Space: O(nW) or O(W) optimized

Q4 (5 Marks): Fractional Knapsack vs 0/1
| Feature | 0/1 Knapsack | Fractional |
|--------------------|-------------------|------------------|
| Can take fraction? | No | Yes |
| Method | DP | Greedy |
| Complexity | O(nW) | O(n log n) |

FINAL TIP FOR EXAM

In 15-mark question:
1. Write recurrence → 4 marks
2. Draw complete table → 8 marks
3. Backtrack to find selected items → 2 marks
4. Write complexity → 1 mark
→ Total 15/15!

You are now 0/1 Knapsack Master!
Want Longest Common Subsequence (LCS) next? Say “LCS”!