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.

Practice

1. In the 0/1 Knapsack problem, why can't we take fractions of items like in the Fractional Knapsack?

easy

A. Because the DP table only stores integers

B. Because each item must be taken as a whole unit or not at all - fractional inclusion violates the problem definition

C. Because fractions make the recursion infinite

D. Because the weight array only accepts integer values

Solution

1. 0/1 Constraint

   The '0/1' in the name literally means each item has two states: not taken (0) or fully taken (1). There is no state for 0.5 or any fraction.

2. Why Greedy Fails

   Because you cannot take fractions, the greedy 'highest value/weight ratio first' strategy fails - taking a high-ratio item may block a better combination of whole items.

3. Why DP is Needed

   DP explores all combinations of 0/1 choices, which is required when greedy fails due to the binary selection constraint.

4. Final Answer:

   Each item is binary - take it whole or skip it. → Option B

Hint: 0/1 = binary choice per item: take it whole or skip entirely. [OK]

Common Mistakes:

• Confusing 0/1 Knapsack with Fractional Knapsack
• Thinking DP table data type restricts selection
• Assuming greedy works for 0/1 Knapsack

2. For 0/1 Knapsack with n=3 items and capacity W=5, what is the size of the standard DP table dp[n+1][W+1] in C?

easy

A. 3 × 5

B. 4 × 5

C. 3 × 6

D. 4 × 6

Solution

1. Table Dimensions

   The DP table is dp[n+1][W+1]. With n=3 items and W=5 capacity: dp[4][6].

2. Why +1

   Index 0 represents the base case: dp[0][w] = 0 (no items) and dp[i][0] = 0 (zero capacity). The +1 makes these base cases fit naturally without off-by-one adjustments.

3. In C

   int dp[4][6]; - 4 rows (0 to 3 items), 6 columns (capacity 0 to 5).

4. Final Answer:

   4 × 6 → Option D

Hint: dp[n+1][W+1] → always add 1 to both dimensions for the base case. [OK]

Common Mistakes:

• Using dp[n][W] and missing the base case row/column
• Adding +1 to only one dimension
• Confusing n items with n+1 rows

3. In the 0/1 Knapsack DP recurrence, when weight[i] > w (current item is heavier than current capacity), what is dp[i][w]?

medium

A. 0

B. dp[i-1][w] - same value as without this item

C. dp[i][w-1]

D. value[i] + dp[i-1][w - weight[i]]

Solution

1. Can't Include Overweight Item

   If weight[i] > w, item i cannot fit - we must skip it.

2. Inherit from Previous Row

   dp[i][w] = dp[i-1][w]: the best value with first i items equals the best with first i-1 items.

3. Full Recurrence

   if (weight[i] > w): dp[i][w] = dp[i-1][w]. else: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])

4. Final Answer:

   dp[i-1][w] → Option B

Hint: Item too heavy → skip → copy from row above: dp[i-1][w]. [OK]

Common Mistakes:

• Setting dp[i][w]=0 instead of carrying forward the previous best
• Applying include formula when item doesn't fit
• Reading dp[i][w-1] instead of dp[i-1][w]

4. What is the time and space complexity of the standard bottom-up 0/1 Knapsack DP solution?

medium

A. Time O(n×W), Space O(n×W)

B. Time O(n×W), Space O(W)

C. Time O(2^n), Space O(n)

D. Time O(n log W), Space O(n×W)

Solution

1. Time Complexity

   Two nested loops: outer over n items, inner over W+1 capacities. Each cell O(1). Total: O(n×W).

2. Space Complexity

   Full table dp[n+1][W+1] → O(n×W) space.

3. Note

   Space can be reduced to O(W) with 1D rolling array, but standard 2D table is O(n×W).

4. Final Answer:

   Time O(n×W), Space O(n×W) → Option A

Hint: Standard 2D table = O(n×W) time AND space. 1D optimized = O(W) space only. [OK]

Common Mistakes:

• Confusing standard O(n×W) space with optimized O(W)
• Claiming O(2^n) which applies only to naive recursion
• Mixing up time and space complexities

5. In the space-optimized 1D 0/1 Knapsack in C, why must the inner capacity loop iterate from W down to weight[i], not from 0 up to W?

hard

A. To avoid negative array indices

B. To prevent using item i more than once - forward iteration would allow the same item to be counted multiple times in the same pass

C. Because C arrays are stored in column-major order

D. To match the order of the weight array

Solution

1. Problem With Left-to-Right

   With a 1D array, processing left to right means dp[w-weight[i]] has already been updated in this pass - item i gets counted again at smaller capacities.

2. Right-to-Left Prevents Reuse

   Iterating from W down to weight[i] ensures dp[w-weight[i]] still holds the pre-item-i value. Each item counted at most once.

3. 0/1 vs Unbounded

   Right-to-left = 0/1 Knapsack. Left-to-right = Unbounded Knapsack.

4. Final Answer:

   Prevents reusing item i in the same pass. → Option B

Hint: Right-to-left = 0/1 (no reuse). Left-to-right = Unbounded (reuse allowed). [OK]

Common Mistakes:

• Using left-to-right which implements Unbounded Knapsack accidentally
• Thinking loop direction is about array bounds not item reuse
• Not knowing right-to-left is the key 0/1 vs Unbounded distinction