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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack DP Table

What is the final maximum value stored in the DP table for the given weights and values?

DSA C++

int 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] = std::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]);
    std::cout << knapsack(W, wt, val, n);
    return 0;
}

A 160

B 220

C 180

D 200

💡 Hint

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

The knapsack can hold items with weights 20 and 30 for a total value of 100 + 120 = 220, which is the maximum possible value without exceeding weight 50.

🧠 Conceptual

intermediate

Understanding the 0 1 Knapsack Problem Constraints

Which statement correctly describes the 0 1 Knapsack problem?

A Each item can be taken at most once to maximize value.

B You can take fractional parts of items to maximize value.

C Each item can be taken multiple times to maximize value.

D Items must be taken in the order they are given.

💡 Hint

Remember the meaning of '0 1' in the problem name.

In the 0 1 Knapsack problem, each item can be chosen either once or not at all, no fractions or repetitions allowed.

🔧 Debug

advanced

Identify the Bug in the Knapsack Recursive Code

What error will this code produce when called with knapsack(50, wt, val, 3)?

DSA C++

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 std::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};
    std::cout << knapsack(50, wt, val, 3);
    return 0;
}

A Stack overflow due to infinite recursion

B Runtime error due to invalid array access

C Compilation error due to missing header

D Correct output 220

💡 Hint

Check the base case and recursive calls carefully.

The recursive code correctly implements the 0 1 Knapsack logic and will output 220 for the given inputs.

❓ Predict Output

advanced

Output of Memoized Knapsack Function

What is the output of the following code snippet?

DSA C++

#include <iostream>
#include <cstring>

int dp[4][51];

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

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    memset(dp, -1, sizeof(dp));
    std::cout << knapsack(50, wt, val, 3);
    return 0;
}

A 200

B 180

C 220

D 150

💡 Hint

Memoization stores results to avoid repeated calculations.

Memoized recursion returns the maximum value 220 for the given weights and values within capacity 50.

🚀 Application

expert

Maximum Number of Items in 0 1 Knapsack

Given the weights and values below and knapsack capacity 50, what is the maximum number of items that can be included in the knapsack while achieving the maximum total value?

DSA C++

int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;

A 2

B 3

C 1

D 0

💡 Hint

Check which combination yields max value and count items used.

The max value 220 is achieved by taking items with weights 20 and 30, so 2 items are included.

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The total weight of items without exceeding the value limit

B. The total value of items without exceeding the weight limit

C. The number of items selected regardless of weight

D. The minimum weight of items selected

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Identify the constraint

   The total weight of selected items must not exceed the given weight limit.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option B

4. Quick Check:

   Maximize value with weight limit = A [OK]

Hint: Maximize value, keep total weight ≤ capacity [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Trying to maximize weight instead of value
• Ignoring the weight constraint

2. Which of the following is the correct way to declare the DP table for the 0 1 Knapsack Problem in C++ if n is number of items and W is max weight?

easy

A. int dp[n+1][W+1];

B. int dp[W+1][n+1];

C. int dp[n][W];

D. int dp[W][n];

Solution

1. Step 1: Understand DP table dimensions

   The DP table stores solutions for items 0 to n and weights 0 to W, so size is (n+1) x (W+1).

2. Step 2: Match correct declaration

   int dp[n+1][W+1]; declares dp with dimensions [n+1][W+1], matching the problem requirements.

3. Final Answer:

   int dp[n+1][W+1]; -> Option A

4. Quick Check:

   DP table size = (n+1) x (W+1) [OK]

Hint: DP table size = items+1 by weight+1 [OK]

Common Mistakes:

• Using dp[n][W] misses base case row/column
• Swapping dimensions incorrectly
• Declaring smaller arrays causing out-of-bound errors

3. What is the output of the following C++ code snippet for 0 1 Knapsack Problem?

int values[] = {60, 100, 120};
int weights[] = {10, 20, 30};
int W = 50;
int n = 3;

int dp[4][51] = {0};

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i-1] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

std::cout << dp[n][W] << std::endl;

medium

A. 160

B. 180

C. 220

D. 250

Solution

1. Step 1: Understand the DP logic

   The code fills dp table to find max value for weight limit 50 with items of given weights and values.

2. Step 2: Calculate max value manually

   Items: (10,60), (20,100), (30,120). Max value for weight 50 is choosing items 2 and 3: 100 + 120 = 220.

3. Final Answer:

   220 -> Option C

4. Quick Check:

   Max value for W=50 = 220 [OK]

Hint: Pick items with max value under weight limit [OK]

Common Mistakes:

• Adding weights instead of values
• Choosing items exceeding weight limit
• Misindexing arrays causing wrong dp values

4. Identify the bug in this 0 1 Knapsack DP code snippet:

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

medium

A. Indexing weights and values with i instead of i-1

B. Loop ranges should start from 0 instead of 1

C. Using std::max instead of a custom max function

D. Not initializing dp array to zero

Solution

1. Step 1: Check array indexing

   Arrays weights and values are zero-indexed, but code uses i which starts at 1, causing out-of-bound or wrong access.

2. Step 2: Correct indexing

   Use weights[i-1] and values[i-1] to access correct elements.

3. Final Answer:

   Indexing weights and values with i instead of i-1 -> Option A

4. Quick Check:

   Zero-based arrays need i-1 index [OK]

Hint: Use i-1 for zero-based arrays in loops starting at 1 [OK]

Common Mistakes:

• Accessing arrays with wrong index causing runtime errors
• Starting loops at 0 but using i-1 indexing
• Ignoring dp initialization

5. Given items with values {20, 5, 10, 40, 15, 25} and weights {1, 2, 3, 8, 7, 4}, and max weight 10, what is the maximum value achievable using 0 1 Knapsack?

hard

A. 75

B. 65

C. 70

D. 60

Solution

1. Step 1: Analyze items and weight limit

   Items: values = {20,5,10,40,15,25}, weights = {1,2,3,8,7,4}, max weight = 10.

2. Step 2: Find best combination under weight 10

   Choose items with weights 1,3,4 (values 20,10,25) total weight 8, value 55; or items 1,2,6 (weights 1,2,4) value 20+5+25=50; best is items 1,4 (weights 1+8=9) value 20+40=60; or items 4 and 6 (8+4=12 >10) invalid; items 1,5,6 (1+7+4=12 >10) invalid; items 1,3,5 (1+3+7=11 >10) invalid; items 2,3,6 (2+3+4=9) value 5+10+25=40; items 1,2,3,6 (1+2+3+4=10) value 20+5+10+25=60; items 1,2,3,5 (1+2+3+7=13 >10) invalid; items 1,2,3,4 (1+2+3+8=14 >10) invalid; items 1,2,6,5 (1+2+4+7=14 >10) invalid; items 1,3,6 (1+3+4=8) value 20+10+25=55; items 1,2,3,6 total value 60 and weight 10 fits exactly.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Max value with weight 10 = 60 [OK]

Hint: Try combinations fitting weight limit, sum max values [OK]

Common Mistakes:

• Ignoring weight limit when summing values
• Missing best combination with multiple items
• Assuming greedy choice works always