0 1 Knapsack Problem in DSA Java - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty knapsack

↓

For each item i

↓

For each capacity w

↓

Check if item i fits (weight[i

Yes No↓

Include item i: value[i

↓

Choose max of include/exclude

↓

Store in dp[i

↓

Repeat for all items and capacities

↓

Final answer in dp[n

We build a table dp where each cell dp[i][w] stores the max value using first i items with capacity w. For each item and capacity, we decide to include or exclude the item based on max value.

Execution Sample

DSA Java

int[] weights = {1, 3, 4};
int[] values = {1, 4, 5};
int capacity = 7;
int[][] dp = new int[4][8];
// Fill dp table
for (int i = 1; i <= 3; i++) {
  for (int w = 1; w <= 7; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}

This code fills a dp table for 3 items and capacity 7 to find max value that fits.

Execution Table

Step	Operation	Item i	Capacity w	Include Value	Exclude Value	dp[i][w]	Table State (dp rows)
1	Initialize dp with zeros	-	-	-	-	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], [0,0,0,0,0,0,0,0]]
2	Item 1, w=1	1	1	1 + dp[0][0]=1	dp[0][1]=0	1	[[0,0,0,0,0,0,0,0], [0,1,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
3	Item 1, w=2	1	2	1 + dp[0][1]=1	dp[0][2]=0	1	[[0,0,0,0,0,0,0,0], [0,1,1,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
4	Item 1, w=3	1	3	1 + dp[0][2]=1	dp[0][3]=0	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
5	Item 1, w=4	1	4	1 + dp[0][3]=1	dp[0][4]=0	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
6	Item 1, w=5	1	5	1 + dp[0][4]=1	dp[0][5]=0	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
7	Item 1, w=6	1	6	1 + dp[0][5]=1	dp[0][6]=0	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
8	Item 1, w=7	1	7	1 + dp[0][6]=1	dp[0][7]=0	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
9	Item 2, w=1	2	1	4 + dp[1][-2]=N/A	dp[1][1]=1	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
10	Item 2, w=2	2	2	4 + dp[1][-1]=N/A	dp[1][2]=1	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
11	Item 2, w=3	2	3	4 + dp[1][0]=4	dp[1][3]=1	4	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,0,0,0,0], [0,0,0,0,0,0,0,0]]
12	Item 2, w=4	2	4	4 + dp[1][1]=5	dp[1][4]=1	5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,0,0,0], [0,0,0,0,0,0,0,0]]
13	Item 2, w=5	2	5	4 + dp[1][2]=5	dp[1][5]=1	5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,0,0], [0,0,0,0,0,0,0,0]]
14	Item 2, w=6	2	6	4 + dp[1][3]=5	dp[1][6]=1	5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,0], [0,0,0,0,0,0,0,0]]
15	Item 2, w=7	2	7	4 + dp[1][4]=5	dp[1][7]=1	5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,0,0,0,0,0,0,0]]
16	Item 3, w=1	3	1	5 + dp[2][-3]=N/A	dp[2][1]=1	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,0,0,0,0,0,0]]
17	Item 3, w=2	3	2	5 + dp[2][-2]=N/A	dp[2][2]=1	1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,0,0,0,0,0]]
18	Item 3, w=3	3	3	5 + dp[2][-1]=N/A	dp[2][3]=4	4	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,0,0,0,0]]
19	Item 3, w=4	3	4	5 + dp[2][0]=5	dp[2][4]=5	5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,0,0,0]]
20	Item 3, w=5	3	5	5 + dp[2][1]=6	dp[2][5]=5	6	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,6,0,0]]
21	Item 3, w=6	3	6	5 + dp[2][2]=6	dp[2][6]=5	6	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,6,6,0]]
22	Item 3, w=7	3	7	5 + dp[2][3]=9	dp[2][7]=5	9	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,6,6,9]]
23	End	-	-	-	-	-	Final max value is dp[3][7] = 9

💡 All items and capacities processed; dp table fully filled; final answer at dp[3][7]

Variable Tracker

Variable	Start	After Step 2	After Step 11	After Step 22	Final
dp	[all zeros]	dp[1][1]=1	dp[2][3]=4	dp[3][7]=9	dp table completed
i (item index)	0	1	2	3	3
w (capacity)	0	1	3	7	7

Key Moments - 3 Insights

Why do we check if weight[i] <= w before including the item?

Because if the item's weight is more than current capacity w, we cannot include it. See execution_table rows 9 and 16 where include value is N/A when weight > w.

Why do we take max of include and exclude values?

We want the best value possible. Including the item adds its value plus leftover capacity value; excluding keeps previous best. See execution_table rows 11 and 22 where dp[i][w] is max of include/exclude.

Why does dp have one extra row and column?

Row 0 and column 0 represent no items or zero capacity, initialized to zero. This simplifies indexing and base cases. See execution_table row 1 initialization.

Visual Quiz - 3 Questions

Look at the execution_table at step 11, what is the dp value for item 2 and capacity 3?

A 1

B 5

C 4

D 0

💡 Hint

Check the 'dp[i][w]' column in execution_table row 11

At which step does the dp value for item 3 and capacity 7 become 9?

A Step 22

B Step 20

C Step 18

D Step 16

💡 Hint

Look at the last row of execution_table where dp[3][7] is updated

If the capacity was reduced to 5, what would be the maximum value after processing all items?

A 5

B 6

C 4

D 1

💡 Hint

Check dp values at capacity 5 in execution_table rows 20 and 21 for item 3

Concept Snapshot

0 1 Knapsack Problem:
- Use dp table dp[n+1][capacity+1]
- dp[i][w] = max value using first i items with capacity w
- For each item i and capacity w:
  if weight[i] <= w: dp[i][w] = max(value[i] + dp[i-1][w-weight[i]], dp[i-1][w])
  else dp[i][w] = dp[i-1][w]
- Final answer at dp[n][capacity]

Full Transcript

The 0 1 Knapsack Problem uses a table dp where dp[i][w] stores the maximum value achievable with the first i items and capacity w. We fill this table row by row, checking for each item if it fits in the current capacity. If it fits, we decide to include or exclude it by comparing values. If it doesn't fit, we exclude it. The table starts with zeros for no items or zero capacity. After filling all rows and columns, the answer is at dp[n][capacity]. This method ensures we consider all combinations efficiently.

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The total value of items without exceeding the weight limit

B. The total weight of items regardless of value

C. The number of items selected

D. The minimum weight of selected items

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Identify the constraint

   The total weight of selected items must not exceed the knapsack's capacity.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option A

4. Quick Check:

   Maximize value under weight limit = The total value of items without exceeding the weight limit [OK]

Hint: Focus on maximizing value, not weight or count [OK]

Common Mistakes:

• Confusing weight maximization with value maximization
• Ignoring the weight limit constraint
• Thinking the problem counts items instead of values

2. Which of the following is the correct way to declare the DP array for the 0 1 Knapsack Problem in Java?

easy

A. int[] dp = new int[n+1];

B. int[][] dp = new int[n+1][W+1];

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

D. int dp = new int[n+1][W+1];

Solution

1. Step 1: Understand DP array dimensions

   We use a 2D array with rows for items (n+1) and columns for weight capacities (W+1).

2. Step 2: Check Java syntax for 2D array

   Correct syntax is int[][] dp = new int[n+1][W+1];

3. Final Answer:

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

4. Quick Check:

   2D array with items and weights = int[][] dp = new int[n+1][W+1]; [OK]

Hint: DP array rows = items+1, columns = capacity+1 [OK]

Common Mistakes:

• Using 1D array instead of 2D
• Swapping dimensions incorrectly
• Wrong Java syntax for array declaration

3. What is the output of the following Java code snippet for 0 1 Knapsack with weights = {1, 3, 4}, values = {10, 40, 50}, capacity = 7?

int[] weights = {1, 3, 4};
int[] values = {10, 40, 50};
int capacity = 7;
int n = weights.length;
int[][] dp = new int[n+1][capacity+1];
for (int i = 1; i <= n; i++) {
  for (int w = 1; w <= capacity; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}
System.out.println(dp[n][capacity]);

medium

A. 80

B. 100

C. 90

D. 50

Solution

1. Step 1: Fill DP table for each item and capacity

   Key values: - Item 1 (w=1, v=10): dp[1][1..7] = 10 - Item 2 (w=3, v=40): dp[2][1..2]=10, dp[2][3]=40, dp[2][4..7]=50 - Item 3 (w=4, v=50): dp[3][1..2]=10, dp[3][3]=40, dp[3][4]=50, dp[3][5..6]=60, dp[3][7]=90 (max(50 + dp[2][3]=90, 50))

2. Step 2: Find maximum value at dp[n][capacity]

   dp[3][7] = 90 (select items 2 and 3: 40 + 50 = 90, weights 3+4=7)

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Max value for capacity 7 = 90 [OK]

Hint: Trace DP table row by row for each item [OK]

Common Mistakes:

• Adding values without checking weight limit
• Confusing indices in arrays
• Forgetting to consider previous dp values

4. Identify the error in this Java code snippet for 0 1 Knapsack and select the fix:

int[] weights = {2, 3, 4};
int[] values = {3, 4, 5};
int capacity = 5;
int n = weights.length;
int[][] dp = new int[n][capacity+1];
for (int i = 1; i <= n; i++) {
  for (int w = 1; w <= capacity; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}

medium

A. Change dp array size to int[n+1][capacity+1]

B. Change loop to start from i = 0

C. Use dp[i][w-1] instead of dp[i-1][w]

D. Remove the if condition inside the loop

Solution

1. Step 1: Check dp array size and indexing

   dp is declared as int[n][capacity+1], but loops use i from 1 to n, accessing dp[i], which causes ArrayIndexOutOfBoundsException.

2. Step 2: Fix dp size to match loop indices

   Declare dp as int[n+1][capacity+1] to allow indexing from 0 to n safely.

3. Final Answer:

   Change dp array size to int[n+1][capacity+1] -> Option A

4. Quick Check:

   Array size must match loop indices [OK]

Hint: DP size = items+1 rows to avoid index errors [OK]

Common Mistakes:

• Using dp size smaller than loop range
• Starting loop from 0 but indexing from 1
• Ignoring array index exceptions

5. Given items with weights = {2, 3, 5, 7}, values = {1, 5, 2, 4}, and capacity = 10, what is the maximum value achievable using 0 1 Knapsack? Also, which items are selected?

hard

A. Maximum value 6; items with weights 7 and 2 selected

B. Maximum value 7; items with weights 2, 3, and 5 selected

C. Maximum value 9; items with weights 3, 5, and 2 selected

D. Maximum value 9; items with weights 3 and 7 selected

Solution

1. Step 1: Calculate maximum value using DP

   Check combinations: - Items 3 and 7 weights sum to 10, values 5 + 4 = 9 (3 weight item value is 5, 7 weight item value is 4) - Items 2,3,5 weights sum to 10, values 1+5+2=8 - Items 3 and 7 give 9 value, better than others - Items 2 and 7 sum weight 9, values 1+4=5 Maximum value is 9 with items 3 and 7.

2. Step 2: Verify selected items

   Selected items are weights 3 and 7 with values 5 and 4 respectively.

3. Final Answer:

   Maximum value 9; items with weights 3 and 7 selected -> Option D

4. Quick Check:

   Max value 9 with weights 3+7 = 10 capacity [OK]

Hint: Check all combinations fitting capacity for max value [OK]

Common Mistakes:

• Adding values without checking total weight
• Selecting items exceeding capacity
• Confusing item weights and values