0 1 Knapsack Problem in DSA Javascript - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty knapsack

↓

Consider each item one by one

↓

For each item, check weight vs capacity

↓

If item fits: choose max of (include or exclude item)

↓

If item doesn't fit: exclude item

↓

Store result in DP table

↓

Move to next item

↓

Repeat until all items considered

↓

Final answer at dp[last_item

We build a table to decide for each item and capacity whether to include or exclude the item to maximize value.

Execution Sample

DSA Javascript

const weights = [1, 3, 4];
const values = [1, 4, 5];
const capacity = 7;

// dp[i][w] = max value using first i items with capacity w
const n = weights.length;
const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));

for (let i = 1; i <= n; i++) {
  for (let w = 0; w <= capacity; w++) {
    if (weights[i - 1] <= w) {
      dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
    } else {
      dp[i][w] = dp[i - 1][w];
    }
  }
}

console.log(dp[n][capacity]); // Output: 9

This code fills a table to find max value for capacity 7 with 3 items.

Execution Table

Step	Item Considered	Capacity	Decision	DP Table Row State	Explanation
0	No items	0 to 7	All zero	[0, 0, 0, 0, 0, 0, 0, 0]	No items means no value for any capacity
1	Item 1 (w=1,v=1)	0	Cannot include	[0]	Capacity 0 means no space
1	Item 1 (w=1,v=1)	1	Include item 1	[0, 1]	Weight 1 fits capacity 1, value 1
1	Item 1 (w=1,v=1)	2	Include item 1	[0, 1, 1]	Capacity 2 can hold item 1, value 1
1	Item 1 (w=1,v=1)	3	Include item 1	[0, 1, 1, 1]	Same logic for capacity 3
1	Item 1 (w=1,v=1)	4	Include item 1	[0, 1, 1, 1, 1]	Same logic for capacity 4
1	Item 1 (w=1,v=1)	5	Include item 1	[0, 1, 1, 1, 1, 1]	Same logic for capacity 5
1	Item 1 (w=1,v=1)	6	Include item 1	[0, 1, 1, 1, 1, 1, 1]	Same logic for capacity 6
1	Item 1 (w=1,v=1)	7	Include item 1	[0, 1, 1, 1, 1, 1, 1, 1]	Same logic for capacity 7
2	Item 2 (w=3,v=4)	0	Cannot include	[0]	Capacity 0 no space
2	Item 2 (w=3,v=4)	1	Exclude item 2	[0, 1]	Weight 3 > capacity 1, keep previous
2	Item 2 (w=3,v=4)	2	Exclude item 2	[0, 1, 1]	Weight 3 > capacity 2, keep previous
2	Item 2 (w=3,v=4)	3	Include item 2	[0, 1, 1, 4]	Include item 2 value 4 better than 1
2	Item 2 (w=3,v=4)	4	Include item 2	[0, 1, 1, 4, 5]	Include item 2 + leftover capacity 1 value 1
2	Item 2 (w=3,v=4)	5	Include item 2	[0, 1, 1, 4, 5, 5]	Same logic for capacity 5
2	Item 2 (w=3,v=4)	6	Include item 2	[0, 1, 1, 4, 5, 5, 5]	Same logic for capacity 6
2	Item 2 (w=3,v=4)	7	Include item 2	[0, 1, 1, 4, 5, 5, 5, 5]	Same logic for capacity 7
3	Item 3 (w=4,v=5)	0	Cannot include	[0]	Capacity 0 no space
3	Item 3 (w=4,v=5)	1	Exclude item 3	[0, 1]	Weight 4 > capacity 1, keep previous
3	Item 3 (w=4,v=5)	2	Exclude item 3	[0, 1, 1]	Weight 4 > capacity 2, keep previous
3	Item 3 (w=4,v=5)	3	Exclude item 3	[0, 1, 1, 4]	Weight 4 > capacity 3, keep previous
3	Item 3 (w=4,v=5)	4	Include item 3	[0, 1, 1, 4, 5]	Include item 3 value 5 better than 4
3	Item 3 (w=4,v=5)	5	Include item 3	[0, 1, 1, 4, 5, 6]	Include item 3 + leftover capacity 1 value 1
3	Item 3 (w=4,v=5)	6	Include item 3	[0, 1, 1, 4, 5, 6, 6]	Include item 3 + leftover capacity 2 value 1
3	Item 3 (w=4,v=5)	7	Include item 3	[0, 1, 1, 4, 5, 6, 6, 9]	Include item 3 + leftover capacity 3 value 4
End	All items considered	Capacity 7	Max value found	[0, 1, 1, 4, 5, 6, 6, 9]	Final answer is 9 at dp[3][7]

💡 All items processed, dp table filled, max value at dp[last_item][capacity]

Variable Tracker

Variable	i=0 (no items)	i=1 (after Item 1)	i=2 (after Item 2)	i=3 (after Item 3)	Final
dp[i] row	[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]	[0,1,1,4,5,6,6,9]
Items considered	None	Item 1 (w=1,v=1)	Items 1-2	Items 1-3	Items 1-3
Capacity	0 to 7	0 to 7	0 to 7	0 to 7	0 to 7

Key Moments - 3 Insights

Why do we sometimes exclude an item even if it fits in the knapsack?

Because including the item might not give the best total value. For example, at Step 2, capacity 3, including item 2 gives value 4 which is better than excluding it (value 1). But at capacity 1 or 2, item 2 is excluded because it doesn't fit.

Why does the DP table have one extra row and column?

The extra row (0 items) and column (capacity 0) represent base cases where no items or no capacity means zero value. This helps build the solution step by step as shown in the first row and first column of the table.

How do we know the final answer is at dp[last_item][capacity]?

Because dp[i][w] stores the max value using first i items with capacity w. After processing all items (i=3) and full capacity (w=7), dp[3][7] holds the max value achievable, which is 9 here.

Visual Quiz - 3 Questions

Look at the execution table, what is the DP table row state after considering Item 2 at capacity 4?

A [0, 1, 1, 1, 1]

B [0, 1, 1, 4, 5]

C [0, 1, 1, 4, 4]

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

💡 Hint

Check the row with Step 2 and Capacity 4 in the execution_table rows.

At which step does the DP table first show a value greater than 1 for capacity 3?

A After Item 1

B After Item 3

C After Item 2

D At start (no items)

💡 Hint

Look at the DP table row states for capacity 3 in execution_table for each item.

If the weight of Item 3 was 5 instead of 4, how would the final dp[3][7] value change?

A It would decrease

B It would increase

C It would remain 9

D It would be zero

💡 Hint

Consider if Item 3 can fit in capacity 7 if weight is 5 and how that affects max value.

Concept Snapshot

0 1 Knapsack Problem:
- Use DP table dp[i][w] for max value with first i items and capacity w
- For each item, either include it (if fits) or exclude it
- dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]]) if fits
- Base case: dp[0][w] = 0 for all w
- Final answer at dp[number_of_items][capacity]

Full Transcript

The 0 1 Knapsack Problem uses a dynamic programming table to find the maximum value that fits in a knapsack of given capacity. We consider items one by one and for each capacity, decide to include or exclude the item based on weight and value. The table dp[i][w] stores the best value using first i items with capacity w. We start with zero items and zero capacity, filling the table row by row. The final answer is at dp[last_item][capacity]. This method ensures we check 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 without exceeding the value limit

C. The number of items selected regardless of weight

D. The minimum weight of items selected

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 weight limit.

3. Final Answer:

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

4. Quick Check:

   Maximize value with weight limit = B [OK]

Hint: Remember: maximize value, not weight or count [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Thinking the problem maximizes number of items
• Ignoring the weight constraint

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

easy

A. const dp = new Array(n + 1).fill(new Array(W + 1).fill(0));

B. const dp = Array(n + 1).fill(Array(W + 1).fill(0));

C. const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));

D. const dp = Array(n).fill(Array(W).fill(0));

Solution

1. Step 1: Understand DP array initialization

   We need a 2D array where each row is a separate array to avoid reference issues.

2. Step 2: Choose correct initialization

   Using Array.from with a function creates independent inner arrays, preventing shared references.

3. Final Answer:

   const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0)); -> Option C

4. Quick Check:

   Independent inner arrays = A [OK]

Hint: Use Array.from with function to avoid shared references [OK]

Common Mistakes:

• Using fill with array directly causing shared references
• Initializing with wrong dimensions
• Forgetting to fill inner arrays

3. What is the output of the following code snippet for weights = [1, 3, 4], values = [15, 50, 60], and W = 5?

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

console.log(knapsack([1, 3, 4], [15, 50, 60], 5));

medium

A. 65

B. 80

C. 60

D. 75

Solution

1. Step 1: Trace DP table filling

   Check items one by one and weights up to 5:
   - Item 1 (weight 1, value 15): dp[1][1..5] = 15
   - Item 2 (weight 3, value 50): dp[2][3] = max(15, 0+50)=50, dp[2][4]=max(15,15+50)=65, dp[2][5]=max(15,15+50)=65
   - Item 3 (weight 4, value 60): dp[3][4]=max(65,0+60)=65, dp[3][5]=max(65,15+60)=75

2. Step 2: Find final answer

   The maximum value for weight 5 is dp[3][5] = 75.

3. Final Answer:

   75 -> Option D

4. Quick Check:

   Max value at W=5 = 75 [OK]

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

Common Mistakes:

• Adding values without checking weight limit
• Confusing indices in dp array
• Forgetting to compare including vs excluding item

4. Identify the bug in this 0 1 Knapsack implementation and select the fix:

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i]] + values[i]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

medium

A. Change weights[i] and values[i] to weights[i - 1] and values[i - 1]

B. Change loop to start i from 0 instead of 1

C. Initialize dp with zeros using fill(1)

D. Change inner loop to run from w = 0 to W - 1

Solution

1. Step 1: Identify index error in array access

   Arrays in JavaScript are zero-indexed, but loop starts at 1, so weights[i] accesses out-of-bound or wrong element.

2. Step 2: Correct index usage

   Use weights[i - 1] and values[i - 1] to access correct item corresponding to dp row i.

3. Final Answer:

   Change weights[i] and values[i] to weights[i - 1] and values[i - 1] -> Option A

4. Quick Check:

   Fix index offset = D [OK]

Hint: Remember dp row i corresponds to item i-1 [OK]

Common Mistakes:

• Using wrong indices causing undefined values
• Changing loop start incorrectly
• Incorrect dp initialization

5. Given items with weights = [2, 3, 5, 7], values = [10, 5, 15, 7], and knapsack capacity W = 10, which set of items maximizes value without exceeding weight? Select the correct maximum value.
Note: You can only take each item once.

hard

A. 25

B. 30

C. 27

D. 22

Solution

1. Step 1: Consider all item combinations within weight limit 10

   Possible combinations:
   - Items 1,2,3: weights 2+3+5=10, values 10+5+15=30 (exceeds capacity? No, equals 10)
   - Items 1,3,4: weights 2+5+7=14 (exceeds 10)
   - Items 2,3,4: weights 3+5+7=15 (exceeds 10)
   - Items 1,4: weights 2+7=9, values 10+7=17
   - Items 3 alone: weight 5, value 15
   - Items 1,2,4: weights 2+3+7=12 (exceeds 10)

2. Step 2: Find max value without exceeding weight

   Best valid combination is items 1,2,3 with total weight 10 and value 30. But since weight is exactly 10, it's valid.
   Check if any other combination gives more value:
   Items 1,3: weight 7, value 25
   Items 3,4: weight 12 (exceeds)
   So max value is 30.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   Max value with W=10 = 30 [OK]

Hint: Try all combos within weight limit to find max value [OK]

Common Mistakes:

• Ignoring exact weight limit equality
• Adding values of items exceeding capacity
• Missing best combination