Unbounded Knapsack Problem in DSA Go

Mental Model

We want to fill a bag with items to get the most value, and we can use each item as many times as we want.

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to enjoy the most tastiness, and you can pick any candy multiple times.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]
Backpack: [ ] -> [ ] -> [ ] -> [ ] -> [ ] -> null
Each slot can hold weight up to capacity.

Dry Run Walkthrough

Input: items: [(weight=1, value=10), (weight=3, value=40), (weight=4, value=50)], capacity=5

Goal: Find the maximum value we can get by filling the backpack with unlimited items without exceeding capacity 5

Step 1: Initialize dp array with size capacity+1, dp[0]=0, others 0

dp: [0, 0, 0, 0, 0, 0]

Why: Start with zero capacity having zero value

Step 2: For capacity=1, check each item if it fits and update dp[1]

dp: [0, 10, 0, 0, 0, 0]

Why: Item with weight 1 fits, value 10 is better than 0

Step 3: For capacity=2, check each item: item1 fits twice, update dp[2]

dp: [0, 10, 20, 0, 0, 0]

Why: Two items of weight 1 give value 20, better than 0

Step 4: For capacity=3, check items: item2 fits, value 40 better than dp[3]

dp: [0, 10, 20, 40, 0, 0]

Why: Item with weight 3 and value 40 is better than three times item1 (30)

Step 5: For capacity=4, check items: item3 fits, value 50 better than dp[4]

dp: [0, 10, 20, 40, 50, 0]

Why: Item with weight 4 and value 50 is best for capacity 4

Step 6: For capacity=5, check items: item1 + dp[4] = 10+50=60 best

dp: [0, 10, 20, 40, 50, 60]

Why: Using item1 plus best for capacity 4 gives max value 60

Result:

dp array: [0, 10, 20, 40, 50, 60]
Maximum value for capacity 5 is 60

Annotated Code

DSA Go

package main

import "fmt"

type Item struct {
	weight int
	value  int
}

func unboundedKnapsack(items []Item, capacity int) int {
	dp := make([]int, capacity+1)
	for c := 1; c <= capacity; c++ {
		maxVal := 0
		for _, item := range items {
			if item.weight <= c {
				val := item.value + dp[c-item.weight]
				if val > maxVal {
					maxVal = val
				}
			}
		}
		dp[c] = maxVal
	}
	return dp[capacity]
}

func main() {
	items := []Item{{1, 10}, {3, 40}, {4, 50}}
	capacity := 5
	maxValue := unboundedKnapsack(items, capacity)
	fmt.Printf("Maximum value for capacity %d is %d\n", capacity, maxValue)
}

for c := 1; c <= capacity; c++ {

Iterate through all capacities from 1 to max capacity

for _, item := range items {

Check each item to see if it fits in current capacity

if item.weight <= c {

Only consider items that fit in current capacity

val := item.value + dp[c-item.weight]

Calculate value if we include this item plus best for remaining capacity

if val > maxVal { maxVal = val }

Update max value for this capacity if better

dp[c] = maxVal

Store best value found for capacity c

Output

Maximum value for capacity 5 is 60

Complexity Analysis

Time: O(n * capacity) because we check each item for every capacity up to the max

Space: O(capacity) because we store max values for each capacity in dp array

vs Alternative: Compared to recursive exponential approach, this dynamic programming solution is much faster and avoids repeated calculations

Edge Cases

capacity = 0

Returns 0 because no items can be added

DSA Go

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

items list empty

Returns 0 because no items to choose from

DSA Go

for _, item := range items {

item weight greater than capacity

Item is skipped because it cannot fit

DSA Go

if item.weight <= c {

When to Use This Pattern

When you can use unlimited copies of items to maximize value within a capacity, use the Unbounded Knapsack pattern because it handles repeated item usage efficiently.

Common Mistakes

Mistake: Using 0/1 Knapsack logic that only allows one copy per item
Fix: Allow repeated use by adding item value plus dp of remaining capacity instead of skipping duplicates

Mistake: Not initializing dp array properly leading to wrong base cases
Fix: Initialize dp[0] = 0 and build up from there

Summary

Find the maximum value achievable with unlimited copies of given items within a capacity.

Use when you can pick items multiple times to fill a capacity for maximum value.

The key is to build solutions for all capacities by reusing previous results and allowing repeated items.

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