0 1 Knapsack Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack Recursive Solution

What is the output of the following C code that solves the 0 1 Knapsack problem using recursion?

DSA C

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0)
        return 0;
    if (wt[n-1] > W)
        return knapsack(W, wt, val, n-1);
    else
        return max(val[n-1] + knapsack(W - wt[n-1], wt, val, n-1), knapsack(W, wt, val, n-1));
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d\n", knapsack(W, wt, val, n));
    return 0;
}

A 180

B 220

C 160

D 200

💡 Hint

Think about which items fit in the knapsack without exceeding the weight limit and maximize value.

The best combination is items with weights 20 and 30 (values 100 + 120 = 220), which fits exactly into the knapsack of capacity 50.

❓ Predict Output

intermediate

Output of 0 1 Knapsack Dynamic Programming Table

What is the value stored in dp[3][50] after running the following dynamic programming code for 0 1 Knapsack?

DSA C

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsackDP(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[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d\n", knapsackDP(W, wt, val, n));
    return 0;
}

A 180

B 150

C 220

D 200

💡 Hint

The dp table stores maximum values for subproblems; dp[n][W] is the answer.

The dp table computes maximum value for capacity 50 and 3 items, which is 220 by choosing items with weights 20 and 30.

🧠 Conceptual

advanced

Time Complexity of 0 1 Knapsack DP Solution

What is the time complexity of the dynamic programming solution for the 0 1 Knapsack problem with n items and capacity W?

A O(n * W)

B O(n + W)

C O(n^2 * W)

D O(2^n)

💡 Hint

Consider the size of the dp table and how many operations fill it.

The dp table has size (n+1)*(W+1), and each cell is computed in constant time, so total time is O(n*W).

🔧 Debug

advanced

Identify the Bug in 0 1 Knapsack DP Implementation

What error will the following code produce when compiled and run?

DSA C

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsackDP(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[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d\n", knapsackDP(W, wt, val, n));
    return 0;
}

A Compilation error: array size must be constant

B Runtime error: segmentation fault

C Logical error: wrong output value

D No error, outputs 220

💡 Hint

Check how the dp array is declared with variable sizes.

In C, arrays declared with variable sizes like dp[n][W] are not allowed in standard C (unless using VLAs in C99). Also, dp should be sized dp[n+1][W+1] to avoid out-of-bounds access.

🚀 Application

expert

Maximum Value and Items Selected in 0 1 Knapsack

Given the following code, what is the printed output showing the maximum value and the items selected (by their indices) for the knapsack problem?

DSA C

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

void 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];
        }
    }
    int res = dp[n][W];
    printf("Maximum value: %d\n", res);

    int w = W;
    printf("Items selected: ");
    for (int i = n; i > 0 && res > 0; i--) {
        if (res != dp[i-1][w]) {
            printf("%d ", i-1);
            res -= val[i-1];
            w -= wt[i-1];
        }
    }
    printf("\n");
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    knapsack(W, wt, val, n);
    return 0;
}

A

Maximum value: 220
Items selected: 0 2 

B

Maximum value: 220
Items selected: 1 2 

C

Maximum value: 180
Items selected: 1 0 

D

Maximum value: 220
Items selected: 2 1 

💡 Hint

Trace back from dp[n][W] to find which items were included.

The maximum value is 220 by selecting items with indices 2 and 1 (weights 30 and 20). The code prints indices in descending order as found during backtracking.