0/1 KNAPSACK – FULL DP CODE (Most Asked in Practical + Theory Exam – 15 Marks Guaranteed!)

Here are 3 versions – all 100% working, exam-ready, with output!

0/1 KNAPSACK – FULL DP CODE (Most Asked in Practical + Theory Exam

0/1 KNAPSACK – FULL DP CODE (Most Asked in Practical + Theory Exam – 15 Marks Guaranteed!)

Here are 3 versions – all 100% working, exam-ready, with output!

VERSION 1 – CLASSIC 2D DP (Most Common in Exams)

#include<stdio.h>
#include<string.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];

    // Build table dp[][] in bottom-up manner
    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];
}

// Bonus: Print selected items (very high marks!)
void printItems(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++) {
        for(int w = 1; w <= W; w++) {
            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];
        }
    }

    // Backtrack to find which 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[] = {60, 100, 120};
    int wt[]  = {10,  20,  30};
    int W = 50;
    int n = 3;

    printf("Maximum Profit = %d\n", knapsack(W, wt, val, n));
    printItems(W, wt, val, n);

    return 0;
}

Output:

Maximum Profit = 220
Selected items: 3 2

VERSION 2 – SPACE OPTIMIZED 1D DP (Advanced – 10 Bonus Marks!)

#include<stdio.h>

int knapsack1D(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] = (dp[w] > val[i] + dp[w - wt[i]]) ? dp[w] : val[i] + dp[w - wt[i]];
        }
    }
    return dp[W];
}

int main() {
    int val[] = {60, 100, 120, 10};
    int wt[]  = {10, 20, 30, 1};
    int W = 10;
    int n = 4;

    printf("Maximum Profit (1D DP) = %d\n", knapsack1D(W, wt, val, n));
    // Output: 60 (R + S from previous example)
    return 0;
}

VERSION 3 – COMPLETE EXAM EXAMPLE (Draw Table + Run Code)

Items:
| Item | Value | Weight |
|------|-------|--------|
| 1 | 10 | 2 |
| 2 | 10 | 3 |
| 3 | 12 | 4 |
| W = 5

DP Table (Draw This!)

i\w	2	3	4	5
0	0	0	0	0
1	10	10	10	10
2	10	10	10	20
3	10	10	12	20

Answer = 20 (items 1 and 2)

Run Code:

int main() {
    int val[] = {10, 10, 12};
    int wt[]  = {2,  3,  4};
    int W = 5, n = 3;
    printf("Max Profit = %d\n", knapsack(W, wt, val, n));
    // Output: 20
}

TIME & SPACE COMPLEXITY (Write This!)

Version	Time	Space
2D DP	O(nW)	O(nW)
1D DP	O(nW)	O(W)

FINAL EXAM TIP (15 Marks Question)

Write recurrence → 4 marks
Draw full table → 6 marks
Write 2D code → 3 marks
Mention 1D optimization → 2 marks
→ 15/15

You now have bulletproof 0/1 Knapsack DP code + table + explanation!

Want Coin Change, Egg Dropping, or Longest Palindromic Subsequence next?
Or ready for Backtracking Unit?
You’re absolutely dominating DP!

Last updated: Nov 28, 2025

0/1 KNAPSACK – FULL DP CODE (Most Asked in Practical + Theory Exam – 15 Marks Guaranteed!)

Here are 3 versions – all 100% working, exam-ready, with output!