Unbounded Knapsack Problem in DSA Javascript - Execution Trace

Concept Flow - Unbounded Knapsack Problem

Start with empty DP array

↓

For each capacity from 1 to W

↓

For each item

↓

If item weight <= capacity

↓

Update DP[capacity

↓

Repeat for all capacities

↓

DP[W

↓

Return DP[W

We build a table where each capacity stores the best value possible by trying all items repeatedly.

Execution Sample

DSA Javascript

const W = 5;
const items = [{w:1,v:2},{w:2,v:4}];
const dp = Array(W+1).fill(0);
for(let cap=1; cap<=W; cap++) {
  for(const item of items) {
    if(item.w <= cap) dp[cap] = Math.max(dp[cap], dp[cap - item.w] + item.v);
  }
}
console.log(dp[W]);

Calculates max value for capacity 5 with items (weight=1,value=2) and (weight=2,value=4) using unbounded knapsack.

Execution Table

Step	Operation	Capacity	Item (w,v)	DP Before	DP After	Visual DP Array
1	Initialize DP	-	-	-	-	[0,0,0,0,0,0]
2	Capacity=1, Item (1,2)	1	(1,2)	[0,0,0,0,0,0]	[0,2,0,0,0,0]	[0,2,0,0,0,0]
3	Capacity=1, Item (2,4)	1	(2,4)	[0,2,0,0,0,0]	[0,2,0,0,0,0]	[0,2,0,0,0,0]
4	Capacity=2, Item (1,2)	2	(1,2)	[0,2,0,0,0,0]	[0,2,2,0,0,0]	[0,2,2,0,0,0]
5	Capacity=2, Item (2,4)	2	(2,4)	[0,2,2,0,0,0]	[0,2,4,0,0,0]	[0,2,4,0,0,0]
6	Capacity=3, Item (1,2)	3	(1,2)	[0,2,4,0,0,0]	[0,2,4,6,0,0]	[0,2,4,6,0,0]
7	Capacity=3, Item (2,4)	3	(2,4)	[0,2,4,6,0,0]	[0,2,4,6,0,0]	[0,2,4,6,0,0]
8	Capacity=4, Item (1,2)	4	(1,2)	[0,2,4,6,0,0]	[0,2,4,6,8,0]	[0,2,4,6,8,0]
9	Capacity=4, Item (2,4)	4	(2,4)	[0,2,4,6,8,0]	[0,2,4,6,8,0]	[0,2,4,6,8,0]
10	Capacity=5, Item (1,2)	5	(1,2)	[0,2,4,6,8,0]	[0,2,4,6,8,10]	[0,2,4,6,8,10]
11	Capacity=5, Item (2,4)	5	(2,4)	[0,2,4,6,8,10]	[0,2,4,6,8,10]	[0,2,4,6,8,10]
12	End	-	-	-	-	DP[5] = 10, max value for capacity 5

💡 All capacities processed; DP array fully computed.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	Final
dp	[0,0,0,0,0,0]	[0,2,0,0,0,0]	[0,2,4,0,0,0]	[0,2,4,6,8,0]	[0,2,4,6,8,10]	[0,2,4,6,8,10]
cap	N/A	1	2	4	5	5
item	N/A	(1,2)	(2,4)	(1,2)	(2,4)	N/A

Key Moments - 3 Insights

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

Because we try all items for each capacity to find the best value. See steps 4 and 5 where dp[2] is first updated to 2 then updated to 4 after checking both items.

Why can we use dp[capacity - item_weight] when updating dp[capacity]?

Because dp array stores max values for smaller capacities already computed. We build up from smaller to larger capacities as shown in the visual DP array column.

Why does the DP array have length W+1?

Because we include capacity 0 (no capacity) as base case. This is shown in step 1 where dp starts as [0,0,0,0,0,0].

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the DP array after processing capacity 3 with item (1,2)?

A [0,2,4,6,0,0]

B [0,2,4,4,0,0]

C [0,2,4,2,0,0]

D [0,0,0,6,0,0]

💡 Hint

Check the 'DP After' and 'Visual DP Array' columns at step 6 in the execution table.

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

A Capacity 3

B Capacity 4

C Capacity 5

D Capacity 2

💡 Hint

Look at the 'Visual DP Array' column in steps 8 and 9.

If we remove the item with weight 1 and value 2, what would be the DP value at capacity 5?

A 10

B 4

C 8

D 0

💡 Hint

Without the smaller item, only multiples of weight 2 item count; check dp updates at capacity 5.

Concept Snapshot

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

Full Transcript

The unbounded knapsack problem finds the maximum value achievable with unlimited copies of given items within a capacity limit. We use a dynamic programming array dp where dp[c] stores the best value for capacity c. Starting from capacity 1 to W, for each item, if the item weight fits, we update dp[c] by comparing current dp[c] and dp[c - item_weight] plus item value. This way, we build solutions from smaller capacities to larger ones. The final answer is dp[W]. The execution table shows step-by-step how dp array changes as we process each capacity and item. Key moments clarify why dp updates multiple times per capacity and why dp array length is W+1. The visual quiz tests understanding of dp array states and effects of item removal.

Practice

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

easy

A. Unbounded Knapsack uses recursion while 0/1 Knapsack uses iteration

B. In Unbounded Knapsack each item can be chosen any number of times; in 0/1 each item is chosen at most once

C. Unbounded Knapsack has no weight constraint

D. 0/1 Knapsack allows fractional items while Unbounded does not

Solution

1. Step 1: Understand 0/1 constraint

   In 0/1 Knapsack each item has a binary choice - include once or exclude. After including, it cannot be reused.

2. Step 2: Understand Unbounded constraint

   In Unbounded Knapsack there is no limit on how many times an item can be selected. The same item can fill the bag.

3. Step 3: Practical impact

   This changes the recurrence: 0/1 uses dp[i-1][w-wt] (previous row); Unbounded uses dp[i][w-wt] (same row, enabling reuse).

4. Final Answer:

   Unbounded allows unlimited item repetition. -> Option B

5. Quick Check:

   Unbounded = unlimited copies. 0/1 = at most one per item. [OK]

Hint: Unbounded = unlimited copies. 0/1 = at most one copy per item. [OK]

Common Mistakes:

• Confusing Unbounded with Fractional Knapsack
• Thinking 0/1 allows unlimited items
• Believing recursion vs iteration distinguishes them

2. In the 1D bottom-up Unbounded Knapsack solution, why does the inner loop go left-to-right (from weight[i] to W)?

medium

A. Left-to-right is faster in JavaScript due to array caching

B. Left-to-right allows the same item to be reused in one pass - exactly what Unbounded Knapsack requires

C. Right-to-left would cause negative indices

D. Left-to-right matches the order of the items array

Solution

1. Step 1: Left-to-right reuse

   Computing dp[w] using dp[w - weight[i]] left-to-right means dp[w - weight[i]] has already been updated - it reflects using item i again. This is intentional reuse.

2. Step 2: Contrast with 0/1

   0/1 Knapsack goes right-to-left to prevent reuse - ensuring dp[w - weight[i]] holds the pre-item value.

3. Final Answer:

   Left-to-right enables intentional item reuse. -> Option B

4. Quick Check:

   Left-to-right = reuse. Right-to-left = no reuse. [OK]

Hint: Left-to-right = reuse allowed (Unbounded). Right-to-left = no reuse (0/1). [OK]

Common Mistakes:

• Thinking direction affects performance not semantics
• Not knowing left-to-right enables reuse
• Confusing with 0/1 which requires right-to-left

3. Given items with weights [1, 3, 4] and values [10, 40, 50] and capacity W=6, what is the maximum value for Unbounded Knapsack?

medium

A. 60

B. 80

C. 90

D. 100

Solution

1. Step 1: Try repeating each item

   Item 1 (w=1, v=10) × 6 = value 60. Item 2 (w=3, v=40) × 2 = value 80, weight=6 exactly. Item 3 (w=4, v=50) + item 1 × 2 = value 70.

2. Step 2: Find maximum

   Two copies of item 2 gives value 80 using exactly capacity 6 - this is the maximum.

3. Final Answer:

   80 -> Option B

4. Quick Check:

   Item 2 × 2: 40×2=80, weight 3×2=6. [OK]

Hint: Try repeating each item to fill capacity: item 2 twice (3×2=6, 40×2=80) wins. [OK]

Common Mistakes:

• Only trying single-item combinations
• Not trying repeated use of the same item
• Confusing with 0/1 where each item used at most once

4. What is the time and space complexity of the optimized 1D Unbounded Knapsack solution?

medium

A. Time O(n×W), Space O(n×W)

B. Time O(2^n), Space O(n)

C. Time O(n×W), Space O(W)

D. Time O(n log W), Space O(W)

Solution

1. Step 1: Time complexity

   Two nested loops - n items × W+1 capacities. Each cell O(1). Total O(n×W).

2. Step 2: Space complexity

   Only a 1D array dp[W+1] is needed, updated in place. Space O(W).

3. Step 3: Contrast with 2D

   Standard 2D DP uses O(n×W) space. 1D optimization reduces to O(W).

4. Final Answer:

   Time O(n×W), Space O(W) -> Option C

5. Quick Check:

   1D = O(n×W) time, O(W) space. [OK]

Hint: 1D Unbounded = O(n×W) time, O(W) space - one array updated in place. [OK]

Common Mistakes:

• Reporting O(n×W) space for 1D version
• Confusing with O(2^n) exponential recursion
• Forgetting 1D reduces space to O(W)

5. Which real-world problem is a direct application of Unbounded Knapsack?

hard

A. Job scheduling where each job can be done only once

B. Coin change - finding minimum coins to make an amount where each denomination can be used unlimited times

C. Activity selection where activities have deadlines

D. Matrix chain multiplication to minimize operations

Solution

1. Step 1: Map coin change to Knapsack

   Coin denominations = item weights. Target amount = capacity W. Each denomination usable unlimited times = Unbounded constraint.

2. Step 2: Rule out other options

   Job scheduling once per job = 0/1 Knapsack. Activity selection = greedy. Matrix chain = interval DP.

3. Final Answer:

   Coin change with unlimited denominations. -> Option B

4. Quick Check:

   Coin change = Unbounded. Coins used unlimited times, amount = capacity. [OK]

Hint: Coin change = Unbounded Knapsack. Each coin denomination reusable, amount is capacity. [OK]

Common Mistakes:

• Mapping job scheduling to Unbounded instead of 0/1
• Not recognizing coin change as Knapsack
• Thinking activity selection uses Unbounded DP