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)

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)

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:
1. Recurrence → 4 marks
2. Full DP table → 8 marks
3. Final value = 57 → 2 marks
4. Selected items = 1,2,3,4 → 2 marks
5. Code snippet → 4 marks
→ 20/20

6. BACKTRACKING & BRANCH AND BOUND (Quick Preview)

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!