Unbounded Knapsack Problem in DSA Java - Execution Trace

Concept Flow - Unbounded Knapsack Problem

Start

↓

Initialize DP array with 0

↓

For each capacity from 1 to W

↓

For each item

↓

If item weight <= capacity

↓

Update DP[capacity

↓

Repeat for all capacities

↓

Result = DP[W

↓

End

We fill a DP array where each index represents capacity. For each capacity, we try all items and update the max value possible by including items multiple times.

Execution Sample

DSA Java

int[] weights = {1, 3, 4};
int[] values = {1, 4, 5};
int W = 7;
int[] dp = new int[W + 1];
for (int cap = 1; cap <= W; cap++) {
  for (int i = 0; i < weights.length; i++) {
    if (weights[i] <= cap) {
      dp[cap] = Math.max(dp[cap], dp[cap - weights[i]] + values[i]);
    }
  }
}
System.out.println(dp[W]);

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

Execution Table

Step	Capacity	Item Tried (weight,value)	DP Before	DP After	Action	DP Array State
1	1	(1,1)	dp[1]=0	dp[1]=max(0, dp[0]+1)=1	Update dp[1]	[0,1,0,0,0,0,0,0]
2	1	(3,4)	dp[1]=1	dp[1]=1	Skip (3>1)	[0,1,0,0,0,0,0,0]
3	1	(4,5)	dp[1]=1	dp[1]=1	Skip (4>1)	[0,1,0,0,0,0,0,0]
4	2	(1,1)	dp[2]=0	dp[2]=max(0, dp[1]+1)=2	Update dp[2]	[0,1,2,0,0,0,0,0]
5	2	(3,4)	dp[2]=2	dp[2]=2	Skip (3>2)	[0,1,2,0,0,0,0,0]
6	2	(4,5)	dp[2]=2	dp[2]=2	Skip (4>2)	[0,1,2,0,0,0,0,0]
7	3	(1,1)	dp[3]=0	dp[3]=max(0, dp[2]+1)=3	Update dp[3]	[0,1,2,3,0,0,0,0]
8	3	(3,4)	dp[3]=3	dp[3]=max(3, dp[0]+4)=4	Update dp[3]	[0,1,2,4,0,0,0,0]
9	3	(4,5)	dp[3]=4	dp[3]=4	Skip (4>3)	[0,1,2,4,0,0,0,0]
10	4	(1,1)	dp[4]=0	dp[4]=max(0, dp[3]+1)=5	Update dp[4]	[0,1,2,4,5,0,0,0]
11	4	(3,4)	dp[4]=5	dp[4]=max(5, dp[1]+4)=5	No change	[0,1,2,4,5,0,0,0]
12	4	(4,5)	dp[4]=5	dp[4]=max(5, dp[0]+5)=5	No change	[0,1,2,4,5,0,0,0]
13	5	(1,1)	dp[5]=0	dp[5]=max(0, dp[4]+1)=6	Update dp[5]	[0,1,2,4,5,6,0,0]
14	5	(3,4)	dp[5]=6	dp[5]=max(6, dp[2]+4)=6	No change	[0,1,2,4,5,6,0,0]
15	5	(4,5)	dp[5]=6	dp[5]=max(6, dp[1]+5)=6	No change	[0,1,2,4,5,6,0,0]
16	6	(1,1)	dp[6]=0	dp[6]=max(0, dp[5]+1)=7	Update dp[6]	[0,1,2,4,5,6,7,0]
17	6	(3,4)	dp[6]=7	dp[6]=max(7, dp[3]+4)=8	Update dp[6]	[0,1,2,4,5,6,8,0]
18	6	(4,5)	dp[6]=8	dp[6]=max(8, dp[2]+5)=8	No change	[0,1,2,4,5,6,8,0]
19	7	(1,1)	dp[7]=0	dp[7]=max(0, dp[6]+1)=9	Update dp[7]	[0,1,2,4,5,6,8,9]
20	7	(3,4)	dp[7]=9	dp[7]=max(9, dp[4]+4)=9	No change	[0,1,2,4,5,6,8,9]
21	7	(4,5)	dp[7]=9	dp[7]=max(9, dp[3]+5)=9	No change	[0,1,2,4,5,6,8,9]

💡 All capacities from 1 to 7 processed with all items; dp[7] = 9 is the max value.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
dp[0]	0	0	0	0	0	0	0	0	0
dp[1]	0	1	1	1	1	1	1	1	1
dp[2]	0	0	2	2	2	2	2	2	2
dp[3]	0	0	0	4	4	4	4	4	4
dp[4]	0	0	0	0	5	5	5	5	5
dp[5]	0	0	0	0	0	6	6	6	6
dp[6]	0	0	0	0	0	0	8	8	8
dp[7]	0	0	0	0	0	0	0	9	9

Key Moments - 3 Insights

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

Because for each capacity, we try all items to find the best value. The dp array updates whenever a better value is found, as shown in steps 7-9 and 19-21 in the execution_table.

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

Because dp[capacity - item_weight] stores the best value for the smaller capacity, allowing us to add the current item's value to it. This is visible in the calculation dp[3] = max(dp[3], dp[0] + 4) at step 8.

Why does the dp array start with all zeros?

Because with zero capacity, no items can be taken, so the value is zero. This base case is essential and shown as dp[0] = 0 throughout the variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 8. What is the value of dp[3] after trying item (3,4)?

A 4

B 3

C 0

D 1

💡 Hint

Check the 'DP After' and 'DP Array State' columns at step 8 in the execution_table.

At which capacity does dp first reach the value 5?

A Capacity 3

B Capacity 5

C Capacity 4

D Capacity 7

💡 Hint

Look at the dp array values in the variable_tracker and execution_table rows for capacities 3, 4, and 5.

If the item with weight 1 and value 1 was removed, how would dp[7] change?

A dp[7] would be 5

B dp[7] would be 9

C dp[7] would be 8

D dp[7] would be 0

💡 Hint

Without the smallest item, dp[7] is still 9, achievable with one (3,4) and one (4,5).

Concept Snapshot

Unbounded Knapsack Problem:
- Use a DP array dp[] where dp[c] = max value for capacity c
- For each capacity c from 1 to W:
  - For each item:
    - If item weight <= c:
      dp[c] = max(dp[c], dp[c - item_weight] + item_value)
- Result is dp[W]
- Items can be used unlimited times

Full Transcript

The Unbounded Knapsack Problem uses a dynamic programming array dp where each index represents a capacity from 0 to W. We start with dp[0] = 0 because no capacity means no items. For each capacity, we try all items. If an item's weight fits in the current capacity, we update dp[capacity] to the maximum of its current value and the value of dp[capacity - item_weight] plus the item's value. This allows using items multiple times. The final answer is dp[W], the maximum value achievable with capacity W. The execution table shows step-by-step updates of dp for capacity 1 to 7 with items of weights 1, 3, and 4 and values 1, 4, and 5 respectively. Key moments clarify why multiple updates happen per capacity and why dp starts with zeros. The visual quiz tests understanding of dp updates and the effect of removing items.

Practice

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

easy

A. In Unbounded Knapsack, items can be chosen multiple times; in 0/1 Knapsack, each item can be chosen only once.

B. Unbounded Knapsack does not consider item weights, while 0/1 Knapsack does.

C. 0/1 Knapsack allows fractional items, Unbounded Knapsack does not.

D. Unbounded Knapsack always has a smaller maximum value 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 unlimited times.

2. Step 2: Compare problem constraints

   Unbounded Knapsack allows multiple copies of the same item, which is the key difference from 0/1 Knapsack.

3. Final Answer:

   In Unbounded Knapsack, items can be chosen multiple times; in 0/1 Knapsack, each item can be chosen only once. -> Option A

4. Quick Check:

   Unbounded = multiple items allowed [OK]

Hint: Remember: Unbounded means unlimited item picks [OK]

Common Mistakes:

• Confusing 0/1 Knapsack with fractional knapsack
• Thinking Unbounded Knapsack disallows repeated items
• Assuming weights are ignored in Unbounded Knapsack

2. Which of the following is the correct syntax to initialize the DP array for Unbounded Knapsack in Java for capacity W?

easy

A. int[] dp = new int[W];

B. int dp = new int[W];

C. int[] dp = new int[W+1];

D. int dp[] = new int[W-1];

Solution

1. Step 1: Understand array size for capacities

   We need an array to store max values for capacities from 0 to W, so size must be W+1.

2. Step 2: Check Java array syntax

   Correct syntax is int[] dp = new int[W+1]; which creates an integer array of size W+1.

3. Final Answer:

   int[] dp = new int[W+1]; -> Option C

4. Quick Check:

   Array size = W+1 for capacities 0 to W [OK]

Hint: DP array size = capacity + 1 for indexing [OK]

Common Mistakes:

• Using incorrect array size (W or W-1)
• Wrong Java array declaration syntax
• Declaring dp as int instead of int[]

3. What is the output of the following Java code snippet for Unbounded Knapsack?

int[] wt = {2, 3, 4};
int[] val = {15, 20, 30};
int W = 7;
int[] dp = new int[W+1];
for (int i = 0; i <= W; i++) {
    for (int j = 0; j < wt.length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
System.out.println(dp[W]);

medium

A. 50

B. 75

C. 85

D. 90

Solution

1. Step 1: Understand DP array filling

   For each capacity i from 0 to 7, we try all items and update dp[i] with max value including unlimited items.

2. Step 2: Calculate dp values step-by-step

   dp[0]=0; dp[1]=0; dp[2]=max(0, dp[0]+15)=15; dp[3]=max(0, dp[1]+15, dp[0]+20)=20; dp[4]=max(0, dp[2]+15, dp[1]+20, dp[0]+30)=30; dp[5]=max(dp[3]+15=35, dp[2]+20=35, dp[1]+30=30)=35; dp[6]=max(dp[4]+15=45, dp[3]+20=40, dp[2]+30=45)=45; dp[7]=max(dp[5]+15=50, dp[4]+20=50, dp[3]+30=50)=50.

3. Step 3: Recalculate carefully for correct max

   Rechecking dp[7]: dp[7] = max(dp[7], dp[7-2]+15=dp[5]+15=35+15=50, dp[7-3]+20=dp[4]+20=30+20=50, dp[7-4]+30=dp[3]+30=20+30=50) = 50.

4. Final Answer:

   50 -> Option A

5. Quick Check:

   Max value for W=7 is 50 [OK]

Hint: Trace dp array updates for each capacity [OK]

Common Mistakes:

• Miscomputing dp values for capacities
• Ignoring multiple item picks
• Mixing up weights and values

4. Identify the bug in this Unbounded Knapsack Java code snippet:

int[] wt = {1, 3, 4};
int[] val = {10, 40, 50};
int W = 6;
int[] dp = new int[W+1];
for (int i = 0; i < W; i++) {
    for (int j = 0; j < wt.length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
System.out.println(dp[W]);

medium

A. dp array size should be W, not W+1

B. Loop should run i <= W, not i < W

C. Condition should be wt[j] < i, not wt[j] <= i

D. Inner loop should start from 1, not 0

Solution

1. Step 1: Check loop range for capacity i

   The outer loop runs from i=0 to i<W, so it stops at i=5, missing capacity W=6.

2. Step 2: Correct loop condition

   To include capacity W=6, loop should run i <= W, i.e., i from 0 to 6 inclusive.

3. Final Answer:

   Loop should run i <= W, not i < W -> Option B

4. Quick Check:

   Loop must cover capacity W [OK]

Hint: Loop to W inclusive for full capacity coverage [OK]

Common Mistakes:

• Using i < W misses last capacity
• Wrong dp array size causing index errors
• Incorrect condition in if statement

5. Given weights wt = {1, 3, 4}, values val = {10, 40, 50}, and capacity W = 7, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 140

B. 120

C. 110

D. 90

Solution

1. Step 1: Initialize dp array and compute values

   dp[0]=0; For each capacity i from 1 to 7, calculate max value by trying all items multiple times.

2. Step 2: Calculate dp values stepwise

   dp[1]=max(dp[1], dp[0]+10)=10; dp[2]=max(dp[2], dp[1]+10)=20; dp[3]=max(dp[3], dp[0]+40, dp[2]+10)=40; dp[4]=max(dp[4], dp[1]+40, dp[0]+50, dp[3]+10)=50; dp[5]=max(dp[5], dp[2]+40, dp[1]+50, dp[4]+10)=60; dp[6]=max(dp[6], dp[3]+40, dp[2]+50, dp[5]+10)=80; dp[7]=max(dp[7], dp[4]+40, dp[3]+50, dp[6]+10)=90.

3. Step 3: Recalculate carefully for max value

   Check dp[7]: dp[7]=max(dp[7], dp[6]+10=80+10=90, dp[4]+40=50+40=90, dp[3]+50=40+50=90) = 90. But we can try combinations: 3*3 + 1*1 weights = 3+3+1=7, values = 40+40+10=90; or 4+3 weights = 7, values=50+40=90. So max is 90.

4. Final Answer:

   90 -> Option D

5. Quick Check:

   Max value for W=7 is 90 [OK]

Hint: Try all item combos for each capacity [OK]

Common Mistakes:

• Not considering multiple item picks
• Miscomputing dp values for capacities
• Ignoring best combination of items