0 1 Knapsack Problem in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the knapsack capacity variable.

DSA C

int [1] = 50; // Maximum weight capacity of the knapsack

Drag options to blanks, or click blank then click option'

Asize

Bweight

CmaxWeight

Dcapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable names that don't clearly represent knapsack capacity.

Using 'weight' which might confuse with item weight.

The variable capacity is commonly used to represent the maximum weight the knapsack can hold.

2fill in blank

medium

Complete the code to initialize the DP table with zeros.

DSA C

for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= [1]; w++) {
        dp[i][w] = 0;
    }
}

Drag options to blanks, or click blank then click option'

Aweight

Bn

Ccapacity

DmaxWeight

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'n' which is the number of items, not capacity.

Using undefined variables.

The inner loop runs up to the knapsack capacity, so we use capacity here.

3fill in blank

hard

Fix the error in the condition to check if the current item's weight fits in the knapsack.

DSA C

if (wt[i - 1] [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];
}

Drag options to blanks, or click blank then click option'

A<=

B==

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' which is the opposite condition.

Using '==' which excludes items lighter than capacity.

The item can be included only if its weight is less than or equal to the current capacity w.

4fill in blank

hard

Fill both blanks to complete the max function and the loop variable.

DSA C

int max(int a, int b) {
    return (a [1] b) ? a : b;
}

for (int [2] = 1; [2] <= n; [2]++) {
    // loop body
}

Drag options to blanks, or click blank then click option'

A>

B<

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' in max function which returns the smaller value.

Using 'j' as loop variable when 'i' is standard here.

The max function returns the greater of two values using '>'. The loop variable is commonly 'i' for iterating items.

5fill in blank

hard

Fill all three blanks to complete the DP table update inside the nested loops.

DSA C

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= capacity; w++) {
        if (wt[i - 1] [1] w) {
            dp[i][w] = max(val[i - 1] + dp[i - 1][w [2] wt[i - 1]], dp[i - 1][w]);
        } else {
            dp[i][w] = dp[i - 1][w];
        }
    }
}

Drag options to blanks, or click blank then click option'

A<=

B-

C+

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '-' when calculating remaining capacity.

Using '>' in the condition which excludes fitting items.

The condition checks if the item weight is less than or equal to current capacity. The remaining capacity is calculated by subtracting the item's weight. The max function compares two values.