Unbounded Knapsack Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack DP Table

What is the final maximum value returned by this Go function for unbounded knapsack with given weights, values, and capacity?

DSA Go

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 {
                dp[i] = max(dp[i], dp[i-wt[j]]+val[j])
            }
        }
    }
    return dp[W]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func main() {
    weights := []int{2, 3, 4}
    values := []int{40, 50, 60}
    capacity := 8
    fmt.Println(unboundedKnapsack(capacity, weights, values))
}

A 200

B 180

C 160

D 150

💡 Hint

Think about how many times you can pick items to maximize value without exceeding capacity.

The function uses dynamic programming to find the maximum value for capacity 8. The best combination is four items of weight 2 (value 40 each) totaling 160.

🧠 Conceptual

intermediate

Key Difference Between 0/1 and Unbounded Knapsack

Which statement correctly describes the main difference between 0/1 Knapsack and Unbounded Knapsack problems?

A In Unbounded Knapsack, each item can be chosen unlimited times; in 0/1 Knapsack, each item can be chosen at most once.

B In 0/1 Knapsack, items can be divided; in Unbounded Knapsack, items must be taken whole.

C Unbounded Knapsack always has smaller capacity than 0/1 Knapsack.

D 0/1 Knapsack allows unlimited items; Unbounded Knapsack restricts to one per item.

💡 Hint

Think about how many times you can pick the same item in each problem.

Unbounded Knapsack allows multiple picks of the same item, unlike 0/1 Knapsack which allows only one pick per item.

🔧 Debug

advanced

Identify the Error in Unbounded Knapsack Implementation

What error will this Go code produce when running the unbounded knapsack function?

DSA Go

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func unboundedKnapsack(W int, wt []int, val []int) int {
    dp := make([]int, W)
    for i := 0; 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]
}

A No error, runs correctly

B Index out of range panic at dp[i]

C Returns zero always

D Compilation error due to missing import

💡 Hint

Check the size of dp array and the indices accessed.

dp is created with size W, but code accesses dp[W], which is out of range causing panic.

🚀 Application

advanced

Maximum Value for Given Items and Capacity

Given items with weights [1, 3, 4] and values [15, 50, 60], and capacity 7, what is the maximum value achievable using unbounded knapsack?

A 105

B 120

C 110

D 115

💡 Hint

Try combinations of items that fit into capacity 7 with repetition.

The maximum value is 115, achieved by taking two items of weight 3 (value 50 each, total 100) and one item of weight 1 (value 15).

❓ Predict Output

expert

Output of Recursive Unbounded Knapsack with Memoization

What is the output of this Go program that uses recursion with memoization for unbounded knapsack?

DSA Go

package main
import "fmt"
func unboundedKnapsackRec(W int, wt []int, val []int, memo map[int]int) int {
    if W == 0 {
        return 0
    }
    if v, ok := memo[W]; ok {
        return v
    }
    maxVal := 0
    for i := 0; i < len(wt); i++ {
        if wt[i] <= W {
            valWithItem := val[i] + unboundedKnapsackRec(W-wt[i], wt, val, memo)
            if valWithItem > maxVal {
                maxVal = valWithItem
            }
        }
    }
    memo[W] = maxVal
    return maxVal
}
func main() {
    weights := []int{1, 3, 4}
    values := []int{15, 50, 60}
    capacity := 7
    memo := make(map[int]int)
    fmt.Println(unboundedKnapsackRec(capacity, weights, values, memo))
}

A 115

B 110

C 105

D 120

💡 Hint

Memoization stores results for capacities to avoid repeated work.

The recursive function finds max value 115 for capacity 7 with given items, same as iterative solution.

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