Unbounded Knapsack Problem in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP array for the unbounded knapsack problem.

DSA Go

dp := make([]int, [1]+1)

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

AmaxWeight

Bn

CW

Dcapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using number of items n instead of capacity W for dp size.

Forgetting to add 1 to the size.

The DP array size should be based on the maximum weight capacity W, so we create dp with length W+1.

2fill in blank

medium

Complete the code to iterate over all weights from 1 to W.

DSA Go

for w := 1; w <= [1]; w++ {

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

AW

Bn

Clen(weights)

Dcapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using number of items n instead of capacity W.

Looping beyond W.

We iterate weights from 1 to W (maximum capacity) to fill dp array.

3fill in blank

hard

Fix the error in the condition to check if current item weight fits in current capacity.

DSA Go

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 excludes items that exactly fit.

Using > or >= which is incorrect.

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

4fill in blank

hard

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

DSA Go

dp[w] = 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 subtraction.

Adding weight instead of value.

We subtract the item's weight from current capacity and add its value to dp to update maximum value.

5fill in blank

hard

Fill all three blanks to complete the unbounded knapsack function signature and return statement.

DSA Go

func unboundedKnapsack([1] []int, [2] []int, [3] int) int {
    // function body
    return dp[W]
}

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

Aweights

Bvalues

CW

Dcapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong parameter names or order.

Returning wrong dp index.

The function takes weights, values slices and capacity W as inputs and returns the max value.

Practice

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

easy

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

B. Unbounded Knapsack uses a different weight limit than 0/1 Knapsack.

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

D. Unbounded Knapsack always has fewer items 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 multiple times without limit.

2. Step 2: Compare problem constraints

   The key difference is the repetition allowance of items, which changes the approach to solving the problem.

3. Final Answer:

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

4. Quick Check:

   Item repetition rule differs = A [OK]

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

Common Mistakes:

• Confusing item repetition rules
• Thinking 0/1 Knapsack allows multiple picks
• Mixing fractional knapsack with unbounded knapsack

2. Which of the following Go code snippets correctly initializes the DP array for solving the Unbounded Knapsack problem with capacity W?

easy

A. dp := make([]int, W+1)

B. dp := make([]int, W)

C. dp := make([]int, W-1)

D. dp := make([]int, W*2)

Solution

1. Step 1: Understand DP array size requirement

   The DP array stores maximum values for capacities from 0 to W inclusive, so it needs length W+1.

2. Step 2: Check Go slice initialization

   Using make([]int, W+1) creates a slice of length W+1, which covers all capacities including zero.

3. Final Answer:

   dp := make([]int, W+1) -> Option A

4. Quick Check:

   DP array length = W+1 [OK]

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

Common Mistakes:

• Using dp size W instead of W+1
• Using negative or zero size slices
• Confusing capacity with number of items

3. What will be the output of the following Go code snippet for Unbounded Knapsack?

package main
import "fmt"
func unboundedKnapsack(W int, wt []int, val []int) int {
    dp := make([]int, W+1)
    for i := 0; i <= W; i++ {
        for j := 0; j < len(wt); j++ {
            if wt[j] <= i {
                if dp[i] < dp[i-wt[j]] + val[j] {
                    dp[i] = dp[i-wt[j]] + val[j]
                }
            }
        }
    }
    return dp[W]
}
func main() {
    W := 5
    wt := []int{1, 3, 4}
    val := []int{10, 40, 50}
    fmt.Println(unboundedKnapsack(W, wt, val))
}

medium

A. 90

B. 100

C. 50

D. 80

Solution

1. Step 1: Trace DP array updates for capacity 5

   Calculate max value for each capacity: - i=1: max(dp[1], dp[0]+10)=10 - i=2: max(dp[2], dp[1]+10)=20 - i=3: max(dp[3], dp[0]+40, dp[2]+10)=40 - i=4: max(dp[4], dp[1]+40, dp[0]+50)=50 - i=5: max(dp[5], dp[2]+40, dp[1]+50)=90

2. Step 2: Final DP value at capacity 5

   dp[5] = 90, which is the maximum value achievable with unlimited items.

3. Final Answer:

   90 -> Option A

4. Quick Check:

   Max value at W=5 is 90 [OK]

Hint: Check dp updates for each capacity step [OK]

Common Mistakes:

• Ignoring multiple item picks
• Using 0/1 knapsack logic
• Incorrect dp array indexing

4. Identify the bug in the following Go code snippet for Unbounded Knapsack and select the correct fix:

func unboundedKnapsack(W int, wt []int, val []int) int {
    dp := make([]int, W)
    for i := 1; i <= W; i++ {
        for j := 0; j < len(wt); j++ {
            if wt[j] <= i {
                dp[i] = max(dp[i], dp[i-wt[j]] + val[j])
            }
        }
    }
    return dp[W]
}

medium

A. Change dp size to W and loop i from 0 to W-1

B. Change dp size to W-1 and loop i from 1 to W-1

C. Initialize dp with zeros and keep code as is

D. Change dp size to W+1 and loop i from 0 to W inclusive

Solution

1. Step 1: Check dp slice size and indexing

   dp is created with size W, but code accesses dp[W], which is out of range. Also, dp should cover 0 to W inclusive, so size must be W+1.

2. Step 2: Adjust loop range and dp size

   Loop i should start from 0 or 1 and go up to W inclusive. dp size must be W+1 to avoid index errors.

3. Final Answer:

   Change dp size to W+1 and loop i from 0 to W inclusive -> Option D

4. Quick Check:

   dp size = W+1 and loop i ≤ W [OK]

Hint: dp array must cover all capacities including zero [OK]

Common Mistakes:

• Using dp size W but accessing dp[W]
• Looping beyond dp slice length
• Not initializing dp correctly

5. Given items with weights wt = [2, 3, 5] and values val = [50, 70, 100], and a knapsack capacity W = 8, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 200

B. 270

C. 250

D. 220

Solution

1. Step 1: Calculate max values for capacities up to 8

   Calculate dp array stepwise: - i=0: 0 - i=1: 0 (no item fits) - i=2: max(0, dp[0]+50)=50 - i=3: max(0, dp[0]+70)=70 - i=4: max(dp[4], dp[2]+50)=100 - i=5: max(dp[5], dp[0]+100, dp[3]+50)=120 - i=6: max(dp[6], dp[4]+50, dp[3]+70)=170 - i=7: max(dp[7], dp[5]+50, dp[4]+70)=190 - i=8: max(dp[8], dp[6]+50, dp[5]+70, dp[3]+100)=270

2. Step 2: Identify maximum value at capacity 8

   dp[8] = 270 is the highest value achievable with unlimited items.

3. Final Answer:

   270 -> Option B

4. Quick Check:

   Max value at W=8 is 270 [OK]

Hint: Build dp array stepwise considering all items [OK]

Common Mistakes:

• Not considering multiple picks of same item
• Calculating dp values incorrectly
• Ignoring smaller capacity combinations