Unbounded Knapsack Problem in DSA Go - Execution Trace

Concept Flow - Unbounded Knapsack Problem

Start with empty DP array

↓

For each capacity from 0 to W

↓

For each item

↓

If item weight <= capacity

↓

Update DP[capacity

↓

Repeat for all capacities and items

↓

DP[W

↓

Return DP[W

We fill a DP array where each index represents capacity. For each capacity, we try all items and update the max value considering unlimited item usage.

Execution Sample

DSA Go

weights := []int{1, 3, 4}
values := []int{1, 4, 5}
W := 7
DP := make([]int, W+1)
max := func(a, b int) int {
  if a > b {
    return a
  }
  return b
}
for c := 0; c <= W; c++ {
  for i := range weights {
    if weights[i] <= c {
      DP[c] = max(DP[c], DP[c-weights[i]] + values[i])
    }
  }
}

This code computes the max value for capacity 7 using items with weights [1,3,4] and values [1,4,5] allowing unlimited item use.

Execution Table

Step	Operation	Capacity (c)	Item (weight,value)	DP Before	DP Update	DP After	Visual DP Array
1	Initialize DP	-	-	-	-	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]
2	c=0, no update	0	-	[0,0,0,0,0,0,0,0]	-	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]
3	c=1, try item (1,1)	1	(1,1)	[0,0,0,0,0,0,0,0]	max(0, DP[0]+1)=1	[0,1,0,0,0,0,0,0]	[0,1,0,0,0,0,0,0]
4	c=1, try item (3,4)	1	(3,4)	[0,1,0,0,0,0,0,0]	weight>capacity no update	[0,1,0,0,0,0,0,0]	[0,1,0,0,0,0,0,0]
5	c=1, try item (4,5)	1	(4,5)	[0,1,0,0,0,0,0,0]	weight>capacity no update	[0,1,0,0,0,0,0,0]	[0,1,0,0,0,0,0,0]
6	c=2, try item (1,1)	2	(1,1)	[0,1,0,0,0,0,0,0]	max(0, DP[1]+1)=2	[0,1,2,0,0,0,0,0]	[0,1,2,0,0,0,0,0]
7	c=2, try item (3,4)	2	(3,4)	[0,1,2,0,0,0,0,0]	weight>capacity no update	[0,1,2,0,0,0,0,0]	[0,1,2,0,0,0,0,0]
8	c=2, try item (4,5)	2	(4,5)	[0,1,2,0,0,0,0,0]	weight>capacity no update	[0,1,2,0,0,0,0,0]	[0,1,2,0,0,0,0,0]
9	c=3, try item (1,1)	3	(1,1)	[0,1,2,0,0,0,0,0]	max(0, DP[2]+1)=3	[0,1,2,3,0,0,0,0]	[0,1,2,3,0,0,0,0]
10	c=3, try item (3,4)	3	(3,4)	[0,1,2,3,0,0,0,0]	max(3, DP[0]+4)=4	[0,1,2,4,0,0,0,0]	[0,1,2,4,0,0,0,0]
11	c=3, try item (4,5)	3	(4,5)	[0,1,2,4,0,0,0,0]	weight>capacity no update	[0,1,2,4,0,0,0,0]	[0,1,2,4,0,0,0,0]
12	c=4, try item (1,1)	4	(1,1)	[0,1,2,4,0,0,0,0]	max(0, DP[3]+1)=5	[0,1,2,4,5,0,0,0]	[0,1,2,4,5,0,0,0]
13	c=4, try item (3,4)	4	(3,4)	[0,1,2,4,5,0,0,0]	max(5, DP[1]+4)=5	[0,1,2,4,5,0,0,0]	[0,1,2,4,5,0,0,0]
14	c=4, try item (4,5)	4	(4,5)	[0,1,2,4,5,0,0,0]	max(5, DP[0]+5)=5	[0,1,2,4,5,0,0,0]	[0,1,2,4,5,0,0,0]
15	c=5, try item (1,1)	5	(1,1)	[0,1,2,4,5,0,0,0]	max(0, DP[4]+1)=6	[0,1,2,4,5,6,0,0]	[0,1,2,4,5,6,0,0]
16	c=5, try item (3,4)	5	(3,4)	[0,1,2,4,5,6,0,0]	max(6, DP[2]+4)=6	[0,1,2,4,5,6,0,0]	[0,1,2,4,5,6,0,0]
17	c=5, try item (4,5)	5	(4,5)	[0,1,2,4,5,6,0,0]	max(6, DP[1]+5)=6	[0,1,2,4,5,6,0,0]	[0,1,2,4,5,6,0,0]
18	c=6, try item (1,1)	6	(1,1)	[0,1,2,4,5,6,0,0]	max(0, DP[5]+1)=7	[0,1,2,4,5,6,7,0]	[0,1,2,4,5,6,7,0]
19	c=6, try item (3,4)	6	(3,4)	[0,1,2,4,5,6,7,0]	max(7, DP[3]+4)=8	[0,1,2,4,5,6,8,0]	[0,1,2,4,5,6,8,0]
20	c=6, try item (4,5)	6	(4,5)	[0,1,2,4,5,6,8,0]	max(8, DP[2]+5)=8	[0,1,2,4,5,6,8,0]	[0,1,2,4,5,6,8,0]
21	c=7, try item (1,1)	7	(1,1)	[0,1,2,4,5,6,8,0]	max(0, DP[6]+1)=9	[0,1,2,4,5,6,8,9]	[0,1,2,4,5,6,8,9]
22	c=7, try item (3,4)	7	(3,4)	[0,1,2,4,5,6,8,9]	max(9, DP[4]+4)=9	[0,1,2,4,5,6,8,9]	[0,1,2,4,5,6,8,9]
23	c=7, try item (4,5)	7	(4,5)	[0,1,2,4,5,6,8,9]	max(9, DP[3]+5)=9	[0,1,2,4,5,6,8,9]	[0,1,2,4,5,6,8,9]

💡 Completed all capacities up to W=7; DP[7] = 9 is the max value.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	After Step 18	After Step 21	Final
DP	[0,0,0,0,0,0,0,0]	[0,1,0,0,0,0,0,0]	[0,1,2,0,0,0,0,0]	[0,1,2,3,0,0,0,0]	[0,1,2,4,5,0,0,0]	[0,1,2,4,5,6,0,0]	[0,1,2,4,5,6,7,0]	[0,1,2,4,5,6,8,9]	[0,1,2,4,5,6,8,9]

Key Moments - 3 Insights

Why do we update DP[c] multiple times for the same capacity?

Because we try all items for each capacity c, updating DP[c] if using that item improves the value. See execution_table rows 3,4,5 for c=1 where DP[1] updates only once because other items are too heavy.

Why does DP[c] depend on DP[c - item_weight]?

Because to include an item, we add its value to the best solution for the remaining capacity (c - item_weight). This is shown in execution_table row 3 where DP[1] = DP[0] + 1.

How does unbounded knapsack differ from 0/1 knapsack in DP updates?

In unbounded knapsack, we can reuse items unlimited times, so DP[c] can be updated multiple times using the same item. This is why we check all items for every capacity. See execution_table rows 6 and 9 where DP updates accumulate.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the DP array value at capacity 3 after updating with item (3,4)?

A 5

B 3

C 4

D 0

💡 Hint

Check the DP After column at step 10 for capacity 3.

At which capacity does the DP array first reach the value 5?

A Capacity 3

B Capacity 4

C Capacity 5

D Capacity 7

💡 Hint

Look at the Visual DP Array column in execution_table rows 12-14.

If the item with weight 4 and value 5 was removed, what would be the DP value at capacity 7?

A 9

B 8

C 7

D 6

💡 Hint

Without the (4,5) item, max value at capacity 7 comes from repeated (1,1) and (3,4) items, see variable_tracker final DP array.

Concept Snapshot

Unbounded Knapsack Problem:
- Use DP array of size W+1 for capacities 0..W
- For each capacity c, try all items
- If item weight <= c, update DP[c] = max(DP[c], DP[c - weight] + value)
- Items can be used unlimited times
- DP[W] gives max value achievable

Full Transcript

The Unbounded Knapsack Problem uses a dynamic programming array DP where each index represents a capacity from 0 to W. For each capacity, we check all items. If an item's weight fits in the capacity, we update DP[c] to the maximum of its current value and the value of using that item plus the best value for the remaining capacity. This allows unlimited use of items. The final DP[W] holds the maximum value achievable. The execution table shows step-by-step how DP updates for each capacity and item, and the variable tracker shows DP array changes over time.

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