Unbounded Knapsack Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack Recursive Call

What is the output of the following C code snippet that calculates the maximum value for an unbounded knapsack problem with given weights and values?

DSA C

#include <stdio.h>

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

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

int main() {
    int val[] = {10, 40, 50, 70};
    int wt[] = {1, 3, 4, 5};
    int W = 8;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", unboundedKnapsack(W, wt, val, n));
    return 0;
}

A 120

B 110

C 130

D 140

💡 Hint

Think about how many times you can take each item given the weight limit.

The maximum value is 110 by taking the items with weights 5 and 3.

🧠 Conceptual

intermediate

Understanding Unbounded Knapsack Item Selection

In the unbounded knapsack problem, why can items be chosen multiple times compared to the 0/1 knapsack problem?

A Because the problem allows infinite copies of each item to maximize value within weight limit.

B Because the items are divisible into fractions to fill the knapsack.

C Because the knapsack capacity is unlimited.

D Because items must be chosen exactly once.

💡 Hint

Think about the difference in constraints between 0/1 and unbounded knapsack.

Unbounded knapsack allows unlimited copies of each item, unlike 0/1 knapsack where each item can be chosen only once.

❓ Predict Output

advanced

Output of Bottom-Up DP Table for Unbounded Knapsack

What is the printed DP table after running the bottom-up unbounded knapsack code for weights {1, 3, 4} and values {15, 50, 60} with capacity 5?

DSA C

#include <stdio.h>

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

int main() {
    int val[] = {15, 50, 60};
    int wt[] = {1, 3, 4};
    int W = 5;
    int n = 3;
    int dp[6] = {0};

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

    for (int i = 0; i <= W; i++) {
        printf("%d ", dp[i]);
    }
    return 0;
}

A [0, 15, 30, 50, 75, 90]

B [0, 15, 15, 50, 60, 60]

C [0, 15, 30, 45, 60, 75]

D [0, 15, 30, 50, 65, 80]

💡 Hint

Check how dp[w] updates by considering all items for each weight w.

The dp array stores max value for each weight. For weight 5, best is 80 by taking item with weight 3 once and weight 1 twice (50 + 15*2 = 80).

🔧 Debug

advanced

Identify the Bug in Unbounded Knapsack Recursive Code

What error does 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 unboundedKnapsack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0)
        return 0;
    if (wt[n-1] <= W) {
        return max(val[n-1] + unboundedKnapsack(W - wt[n-1], wt, val, n-1),
                   unboundedKnapsack(W, wt, val, n-1));
    } else {
        return unboundedKnapsack(W, wt, val, n-1);
    }
}

int main() {
    int val[] = {10, 40, 50};
    int wt[] = {1, 3, 4};
    int W = 6;
    int n = 3;
    printf("%d", unboundedKnapsack(W, wt, val, n));
    return 0;
}

A The code returns incorrect maximum value because it reduces n when including the item, disallowing multiple picks.

B The code causes infinite recursion and stack overflow.

C The code runs correctly and returns the maximum value 90.

D The code causes a segmentation fault due to invalid array access.

💡 Hint

Check how the recursive call changes the item count when including an item.

In unbounded knapsack, when including an item, n should not decrease because items can be chosen multiple times. Here, n-1 is passed, so items are only chosen once.

🚀 Application

expert

Maximum Value and Item Counts in Unbounded Knapsack

Given weights = {2, 3, 5}, values = {50, 70, 100}, and capacity = 8, what is the maximum value and how many times is the item with weight 3 chosen in the optimal solution?

A Maximum value = 220, item with weight 3 chosen 2 times

B Maximum value = 170, item with weight 3 chosen 2 times

C Maximum value = 200, item with weight 3 chosen 0 times

D Maximum value = 150, item with weight 3 chosen 0 times

💡 Hint

Try combinations of items to fill capacity 8 maximizing value, count how many times weight 3 item is used.

Optimal is four items of weight 2 (50*4=200), item with weight 3 chosen 0 times. Two weight 3 + one weight 2 = 190 < 200. One weight 5 + one weight 3 = 170 < 200.