Unbounded Knapsack Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack Recursive Call

What is the output printed by the following Java code snippet that solves the unbounded knapsack problem recursively?

DSA Java

public class UnboundedKnapsack {
    static int unboundedKnapsack(int W, int[] wt, int[] val, int n) {
        if (n == 0 || W == 0) return 0;
        if (wt[n-1] <= W) {
            return Math.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);
        }
    }
    public static void main(String[] args) {
        int W = 8;
        int[] val = {10, 40, 50, 70};
        int[] wt = {1, 3, 4, 5};
        int n = val.length;
        System.out.println(unboundedKnapsack(W, wt, val, n));
    }
}

A 140

B 130

C 120

D 110

💡 Hint

Think about how many times you can pick items with weight 1 and 3 to maximize value.

The maximum value for weight 8 is 110 by picking the item with weight 5 (value 70) once and the item with weight 3 (value 40) once.

❓ Predict Output

intermediate

Output of Bottom-Up DP Table for Unbounded Knapsack

What is the final maximum value printed by this bottom-up dynamic programming Java code for unbounded knapsack?

DSA Java

public class UnboundedKnapsackDP {
    public static int unboundedKnapsack(int W, int[] wt, int[] val) {
        int[] dp = new int[W + 1];
        for (int i = 0; i <= W; i++) {
            for (int j = 0; j < wt.length; j++) {
                if (wt[j] <= i) {
                    dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
                }
            }
        }
        return dp[W];
    }
    public static void main(String[] args) {
        int W = 7;
        int[] val = {15, 14, 10};
        int[] wt = {1, 5, 3};
        System.out.println(unboundedKnapsack(W, wt, val));
    }
}

A 105

B 110

C 115

D 120

💡 Hint

Try to fill the knapsack with the item of weight 1 as many times as possible.

The best value is 15 * 7 = 105 by taking the item with weight 1 seven times.

🔧 Debug

advanced

Identify the Runtime Error in Unbounded Knapsack Code

Which option will cause a runtime error when running this unbounded knapsack Java code?

DSA Java

public class UnboundedKnapsackBug {
    public static int unboundedKnapsack(int W, int[] wt, int[] val) {
        int[] dp = new int[W];
        for (int i = 0; i <= W; i++) {
            for (int j = 0; j < wt.length; j++) {
                if (wt[j] <= i) {
                    dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
                }
            }
        }
        return dp[W];
    }
    public static void main(String[] args) {
        int W = 5;
        int[] val = {10, 30, 20};
        int[] wt = {1, 3, 2};
        System.out.println(unboundedKnapsack(W, wt, val));
    }
}

A ArrayIndexOutOfBoundsException

B NullPointerException

C No error, prints 80

D ArithmeticException

💡 Hint

Check the size of the dp array and the indices used.

The dp array is of size W (5), but code accesses dp[W] which is dp[5], causing ArrayIndexOutOfBoundsException.

🧠 Conceptual

advanced

Why Use Unbounded Knapsack Instead of 0/1 Knapsack?

Which statement best explains when to use the unbounded knapsack problem instead of the 0/1 knapsack problem?

A When each item can be chosen only once to maximize value within weight limit.

B When items have fractional weights and values.

C When each item can be chosen unlimited times to maximize value within weight limit.

D When the knapsack capacity is unlimited.

💡 Hint

Think about how many times you can pick each item.

Unbounded knapsack allows unlimited copies of each item, unlike 0/1 knapsack which allows only one copy per item.

🚀 Application

expert

Maximum Value and Items Chosen in Unbounded Knapsack

Given weights [2, 3, 5], values [50, 70, 100], and capacity 8, what is the maximum value and which items (by weight) are chosen in the unbounded knapsack solution?

A Maximum value: 170; Items chosen: 3, 3, 2

B Maximum value: 200; Items chosen: 2, 2, 2, 2

C Maximum value: 220; Items chosen: 3, 3, 2

D Maximum value: 150; Items chosen: 5, 2, 2

💡 Hint

Try combinations of items that sum to 8 weight and maximize value.

Choosing four items of weight 2 (value 50 each) gives total weight 8 and value 200, which is maximum.

Practice

1. What is the main difference between the Unbounded Knapsack Problem and the 0/1 Knapsack Problem?

easy

A. In Unbounded Knapsack, items can be chosen multiple times; in 0/1 Knapsack, each item can be chosen only once.

B. Unbounded Knapsack does not consider item weights, while 0/1 Knapsack does.

C. 0/1 Knapsack allows fractional items, Unbounded Knapsack does not.

D. Unbounded Knapsack always has a smaller maximum value than 0/1 Knapsack.

Solution

1. Step 1: Understand item selection rules

   In 0/1 Knapsack, each item can be selected at most once. In Unbounded Knapsack, items can be selected unlimited times.

2. Step 2: Compare problem constraints

   Unbounded Knapsack allows multiple copies of the same item, which is the key difference from 0/1 Knapsack.

3. Final Answer:

   In Unbounded Knapsack, items can be chosen multiple times; in 0/1 Knapsack, each item can be chosen only once. -> Option A

4. Quick Check:

   Unbounded = multiple items allowed [OK]

Hint: Remember: Unbounded means unlimited item picks [OK]

Common Mistakes:

• Confusing 0/1 Knapsack with fractional knapsack
• Thinking Unbounded Knapsack disallows repeated items
• Assuming weights are ignored in Unbounded Knapsack

2. Which of the following is the correct syntax to initialize the DP array for Unbounded Knapsack in Java for capacity W?

easy

A. int[] dp = new int[W];

B. int dp = new int[W];

C. int[] dp = new int[W+1];

D. int dp[] = new int[W-1];

Solution

1. Step 1: Understand array size for capacities

   We need an array to store max values for capacities from 0 to W, so size must be W+1.

2. Step 2: Check Java array syntax

   Correct syntax is int[] dp = new int[W+1]; which creates an integer array of size W+1.

3. Final Answer:

   int[] dp = new int[W+1]; -> Option C

4. Quick Check:

   Array size = W+1 for capacities 0 to W [OK]

Hint: DP array size = capacity + 1 for indexing [OK]

Common Mistakes:

• Using incorrect array size (W or W-1)
• Wrong Java array declaration syntax
• Declaring dp as int instead of int[]

3. What is the output of the following Java code snippet for Unbounded Knapsack?

int[] wt = {2, 3, 4};
int[] val = {15, 20, 30};
int W = 7;
int[] dp = new int[W+1];
for (int i = 0; i <= W; i++) {
    for (int j = 0; j < wt.length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
System.out.println(dp[W]);

medium

A. 50

B. 75

C. 85

D. 90

Solution

1. Step 1: Understand DP array filling

   For each capacity i from 0 to 7, we try all items and update dp[i] with max value including unlimited items.

2. Step 2: Calculate dp values step-by-step

   dp[0]=0; dp[1]=0; dp[2]=max(0, dp[0]+15)=15; dp[3]=max(0, dp[1]+15, dp[0]+20)=20; dp[4]=max(0, dp[2]+15, dp[1]+20, dp[0]+30)=30; dp[5]=max(dp[3]+15=35, dp[2]+20=35, dp[1]+30=30)=35; dp[6]=max(dp[4]+15=45, dp[3]+20=40, dp[2]+30=45)=45; dp[7]=max(dp[5]+15=50, dp[4]+20=50, dp[3]+30=50)=50.

3. Step 3: Recalculate carefully for correct max

   Rechecking dp[7]: dp[7] = max(dp[7], dp[7-2]+15=dp[5]+15=35+15=50, dp[7-3]+20=dp[4]+20=30+20=50, dp[7-4]+30=dp[3]+30=20+30=50) = 50.

4. Final Answer:

   50 -> Option A

5. Quick Check:

   Max value for W=7 is 50 [OK]

Hint: Trace dp array updates for each capacity [OK]

Common Mistakes:

• Miscomputing dp values for capacities
• Ignoring multiple item picks
• Mixing up weights and values

4. Identify the bug in this Unbounded Knapsack Java code snippet:

int[] wt = {1, 3, 4};
int[] val = {10, 40, 50};
int W = 6;
int[] dp = new int[W+1];
for (int i = 0; i < W; i++) {
    for (int j = 0; j < wt.length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
System.out.println(dp[W]);

medium

A. dp array size should be W, not W+1

B. Loop should run i <= W, not i < W

C. Condition should be wt[j] < i, not wt[j] <= i

D. Inner loop should start from 1, not 0

Solution

1. Step 1: Check loop range for capacity i

   The outer loop runs from i=0 to i<W, so it stops at i=5, missing capacity W=6.

2. Step 2: Correct loop condition

   To include capacity W=6, loop should run i <= W, i.e., i from 0 to 6 inclusive.

3. Final Answer:

   Loop should run i <= W, not i < W -> Option B

4. Quick Check:

   Loop must cover capacity W [OK]

Hint: Loop to W inclusive for full capacity coverage [OK]

Common Mistakes:

• Using i < W misses last capacity
• Wrong dp array size causing index errors
• Incorrect condition in if statement

5. Given weights wt = {1, 3, 4}, values val = {10, 40, 50}, and capacity W = 7, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 140

B. 120

C. 110

D. 90

Solution

1. Step 1: Initialize dp array and compute values

   dp[0]=0; For each capacity i from 1 to 7, calculate max value by trying all items multiple times.

2. Step 2: Calculate dp values stepwise

   dp[1]=max(dp[1], dp[0]+10)=10; dp[2]=max(dp[2], dp[1]+10)=20; dp[3]=max(dp[3], dp[0]+40, dp[2]+10)=40; dp[4]=max(dp[4], dp[1]+40, dp[0]+50, dp[3]+10)=50; dp[5]=max(dp[5], dp[2]+40, dp[1]+50, dp[4]+10)=60; dp[6]=max(dp[6], dp[3]+40, dp[2]+50, dp[5]+10)=80; dp[7]=max(dp[7], dp[4]+40, dp[3]+50, dp[6]+10)=90.

3. Step 3: Recalculate carefully for max value

   Check dp[7]: dp[7]=max(dp[7], dp[6]+10=80+10=90, dp[4]+40=50+40=90, dp[3]+50=40+50=90) = 90. But we can try combinations: 3*3 + 1*1 weights = 3+3+1=7, values = 40+40+10=90; or 4+3 weights = 7, values=50+40=90. So max is 90.

4. Final Answer:

   90 -> Option D

5. Quick Check:

   Max value for W=7 is 90 [OK]

Hint: Try all item combos for each capacity [OK]

Common Mistakes:

• Not considering multiple item picks
• Miscomputing dp values for capacities
• Ignoring best combination of items