Module 124

UNIT IV – DYNAMIC PROGRAMMING, BACKTRACKING & BRANCH AND BOUND

Focus: Dynamic Programming (Most Scoring Part)
Full Exam-Ready Package for Knapsack + All Classic DP Problems

1. 0/1 KNAPSACK – KING OF DP (15–20 Marks)

Problem
n items, each with weight wᵢ and value vᵢ
Knapsack capacity = W
Maximize value without exceeding weight.
Item cannot be broken.

Recurrence
dp[i][w] = max value using first i items and 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)

CLASSIC EXAM EXAMPLE (Draw This Table – 10 Marks!)

n = 4, W = 8
Items:
1: (w=2, v=12)
2: (w=1, v=10)
3: (w=3, v=20)
4: (w=2, v=15)

i\w	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	12	12	12	12	12	12	12
2	10	12	22	22	22	22	22	22
3	10	12	22	30	30	32	42	42
4	10	15	25	30	37	40	42	57

Answer = 57
Selected items: 1,2,3,4 (weights 2+1+3+2=8)

FULL C CODE (With Item Printing – Practical Exam)

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

void knapsack(int n,int W,int wt[],int val[]){
    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];
        }
    
    printf("Maximum Value = %d\n",dp[n][W]);
    
    // Print selected items
    printf("Selected items: ");
    int i=n,w=W;
    while(i>0&&w>0){
        if(dp[i][w]!=dp[i-1][w]){
            printf("%d ",i);
            w-=wt[i-1];
        }
        i--;
    }
    printf("\n");
}

int main(){
    int val[]={12,10,20,15};
    int wt[]={2,1,3,2};
    int W=8,n=4;
    knapsack(n,W,wt,val);
    return 0;
}
// Output:
// Maximum Value = 57
// Selected items: 4 3 2 1

2. MATRIX CHAIN MULTIPLICATION (15 Marks)

Dimensions: 10, 30, 5, 60, 20
Answer = 6100
Parenthesization: ((A₁A₂)(A₃A₄))

3. LONGEST COMMON SUBSEQUENCE (LCS)

X = "ABCBDAB", Y = "BDCAB" → LCS = "BCAB" → Length 4

4. ALL CLASSIC DP PROBLEMS – ONE-LINER CHEAT SHEET (Draw in Exam)

Problem	Recurrence	Time	Example Answer
0/1 Knapsack	dp[i][w] = max(take, not take)	O(nW)	57
Matrix Chain	m[i][j] = min over k (m[i][k] + m[k+1][j] + cost)	O(n³)	6100
LCS	if match → 1+diag, else max(up,left)	O(mn)	4
Longest Increasing Subsequence	dp[i] = max over j<i (dp[j]+1 if a[j]<a[i])	O(n²)	4 (1,2,4,5)
Coin Change (Min coins)	dp[w] = min over coins (dp[w−coin] + 1)	O(nW)	3 coins
Edit Distance	min(insert, delete, replace)	O(mn)	3
Egg Dropping	min over x (1 + max(below, above))	O(nk²)	14

5. 20-MARKS SOLVED QUESTION (Copy-Paste Format)

Q: Solve 0/1 Knapsack for following:
Items: (2,12), (1,10), (3,20), (2,15)
W = 8

Answer:

Recurrence → 4 marks
Full DP table → 8 marks
Final value = 57 → 2 marks
Selected items = 1,2,3,4 → 2 marks
Code snippet → 4 marks
→ 20/20

6. BACKTRACKING & BRANCH AND BOUND (Quick Preview)

Topic	Example Problem	Method Used
Backtracking	N-Queens, Sudoku	DFS + Pruning
Branch and Bound	0/1 Knapsack (better)	BFS + Bounding

You now have complete DP unit – ready to score 95–100/100 in theory + practical!

Want Backtracking – N-Queens Full Code + Diagram next?
Or Branch and Bound for Knapsack?
Say “N-QUEENS” or “BRANCH AND BOUND”!
You're unstoppable!