Unbounded Knapsack Problem in DSA Typescript - Execution Trace

Concept Flow - Unbounded Knapsack Problem

Start

↓

Initialize DP array with zeros

↓

For each weight from 1 to W

↓

For each item

↓

If item weight <= current weight

↓

Update DP[current weight

↓

Repeat for all weights and items

↓

Return DP[W

↓

End

We fill a DP array from 0 to W, for each weight we try all items and update max value allowing unlimited item use.

Execution Sample

DSA Typescript

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

Calculates max value for knapsack capacity 7 with items reusable unlimited times.

Execution Table

Step	Operation	Current Weight	Item (w,v)	DP Update	DP Array State
1	Initialize DP array	-	-	-	[0,0,0,0,0,0,0,0]
2	weight=1, item=(1,1)	1	(1,1)	dp[1]=max(0, dp[0]+1)=1	[0,1,0,0,0,0,0,0]
3	weight=1, item=(3,4)	1	(3,4)	No update (3>1)	[0,1,0,0,0,0,0,0]
4	weight=1, item=(4,5)	1	(4,5)	No update (4>1)	[0,1,0,0,0,0,0,0]
5	weight=2, item=(1,1)	2	(1,1)	dp[2]=max(0, dp[1]+1)=2	[0,1,2,0,0,0,0,0]
6	weight=2, item=(3,4)	2	(3,4)	No update (3>2)	[0,1,2,0,0,0,0,0]
7	weight=2, item=(4,5)	2	(4,5)	No update (4>2)	[0,1,2,0,0,0,0,0]
8	weight=3, item=(1,1)	3	(1,1)	dp[3]=max(0, dp[2]+1)=3	[0,1,2,3,0,0,0,0]
9	weight=3, item=(3,4)	3	(3,4)	dp[3]=max(3, dp[0]+4)=4	[0,1,2,4,0,0,0,0]
10	weight=3, item=(4,5)	3	(4,5)	No update (4>3)	[0,1,2,4,0,0,0,0]
11	weight=4, item=(1,1)	4	(1,1)	dp[4]=max(0, dp[3]+1)=5	[0,1,2,4,5,0,0,0]
12	weight=4, item=(3,4)	4	(3,4)	dp[4]=max(5, dp[1]+4)=5	[0,1,2,4,5,0,0,0]
13	weight=4, item=(4,5)	4	(4,5)	dp[4]=max(5, dp[0]+5)=5	[0,1,2,4,5,0,0,0]
14	weight=5, item=(1,1)	5	(1,1)	dp[5]=max(0, dp[4]+1)=6	[0,1,2,4,5,6,0,0]
15	weight=5, item=(3,4)	5	(3,4)	dp[5]=max(6, dp[2]+4)=6	[0,1,2,4,5,6,0,0]
16	weight=5, item=(4,5)	5	(4,5)	dp[5]=max(6, dp[1]+5)=6	[0,1,2,4,5,6,0,0]
17	weight=6, item=(1,1)	6	(1,1)	dp[6]=max(0, dp[5]+1)=7	[0,1,2,4,5,6,7,0]
18	weight=6, item=(3,4)	6	(3,4)	dp[6]=max(7, dp[3]+4)=8	[0,1,2,4,5,6,8,0]
19	weight=6, item=(4,5)	6	(4,5)	dp[6]=max(8, dp[2]+5)=8	[0,1,2,4,5,6,8,0]
20	weight=7, item=(1,1)	7	(1,1)	dp[7]=max(0, dp[6]+1)=9	[0,1,2,4,5,6,8,9]
21	weight=7, item=(3,4)	7	(3,4)	dp[7]=max(9, dp[4]+4)=9	[0,1,2,4,5,6,8,9]
22	weight=7, item=(4,5)	7	(4,5)	dp[7]=max(9, dp[3]+5)=9	[0,1,2,4,5,6,8,9]
23	Return result	-	-	-	Max value = 9

💡 All weights from 1 to 7 processed with all items, dp[7] holds max value 9

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 13	After Step 17	After Step 20	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,4,0,0,0,0]	[0,1,2,4,5,0,0,0]	[0,1,2,4,5,6,8,0]	[0,1,2,4,5,6,8,9]	[0,1,2,4,5,6,8,9]
weight	N/A	1	2	3	4	6	7	7

Key Moments - 3 Insights

Why do we update dp[weight] multiple times for different items at the same weight?

Because each item can be used unlimited times, we check all items to find the best value for dp[weight]. See execution_table rows 8-10 where dp[3] updates twice.

Why do we use dp[weight - item.w] + item.v to update dp[weight]?

This means we add the current item's value to the best value for the remaining weight after taking this item. See execution_table row 9 where dp[3] = max(3, dp[0]+4).

Why does dp array start with zeros and length W+1?

dp[i] stores max value for weight i. Starting with zeros means no items taken yet. Length W+1 covers weights from 0 to W inclusive. See execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the value of dp[3] after processing item (3,4)?

A 3

B 4

C 0

D 1

💡 Hint

Check the DP Update column at step 9 in execution_table

At which step does dp[5] first get updated to 6?

A Step 14

B Step 15

C Step 16

D Step 13

💡 Hint

Look for dp[5] updates in execution_table rows 14-16

If we remove the item (1,1), how would dp[7] change at the end?

A It would stay 9

B It would decrease

C It would increase

D It would be zero

💡 Hint

Without the smallest weight item, fewer combinations exist to fill weight 7, see variable_tracker dp values

Concept Snapshot

Unbounded Knapsack:
- dp array size W+1, dp[i] = max value for weight i
- For each weight 1..W, try all items
- If item weight <= current weight, dp[i] = max(dp[i], dp[i - item.w] + item.v)
- Items can be used unlimited times
- Result is dp[W]

Full Transcript

The Unbounded Knapsack problem finds the maximum value achievable with unlimited copies of given items within a weight limit W. We use a dp array where dp[i] stores the max value for weight i. Starting from 0 to W, for each weight, we try all items. If an item's weight fits, we update dp[i] by comparing current dp[i] and dp[i - item weight] plus item value. This allows repeated use of items. After filling dp, dp[W] holds the answer. The execution table shows step-by-step updates of dp array for W=7 and items (1,1), (3,4), (4,5). Key moments clarify why multiple updates per weight happen and why dp array starts with zeros. The visual quiz tests understanding of dp updates and effects of removing items.