Unbounded Knapsack Problem in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp array for the unbounded knapsack.

DSA Java

int[] dp = new int[[1] + 1];

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

Acapacity

Bweights.length

C0

Dvalues.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using the length of weights or values arrays instead of capacity.

Initializing dp with zero size.

The dp array size should be capacity + 1 to store maximum values for all capacities from 0 to capacity.

2fill in blank

medium

Complete the code to iterate over all capacities in the unbounded knapsack solution.

DSA Java

for (int w = 1; w <= [1]; w++) {

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

Aweights.length

Bcapacity

Cvalues.length

Ddp.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using weights.length or values.length instead of capacity.

Looping beyond the dp array size.

The loop should run from 1 to capacity to consider all possible weights.

3fill in blank

hard

Fix the error in the condition to check if the current item can fit in the knapsack.

DSA Java

if (weights[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 checks the opposite condition.

Using '==' which is too restrictive.

The item weight must be less than or equal to the current capacity to fit.

4fill in blank

hard

Fill both blanks to update dp[w] with the maximum value including the current item.

DSA Java

dp[w] = Math.max(dp[w], dp[w - [1]] + [2]);

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

Aweights[i]

Bvalues[i]

Cw

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using w instead of weights[i] in the subtraction.

Adding weight instead of value.

Subtract the weight of the current item from w to find the remaining capacity, then add the item's value.

5fill in blank

hard

Fill all three blanks to complete the nested loops for unbounded knapsack.

DSA Java

for (int i = 0; i < [1]; i++) {
    for (int w = [2]; w <= [3]; w++) {

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

Aweights.length

B1

Ccapacity

Dvalues.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using values.length instead of weights.length for outer loop.

Starting inner loop from 0 instead of 1.

The outer loop runs over all items, the inner loop runs from 1 to capacity to consider all weights.

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