0 1 Knapsack Problem in DSA Typescript - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty DP table

↓

For each item i

↓

For each weight w from 0 to max

↓

Check if item i fits in weight w

↓

Include item i: value = val[i

↓

Exclude item i: value = dp[i-1

↓

Choose max(include, exclude)

↓

Fill dp[i

↓

Repeat for all items and weights

↓

Answer = dp[last_item

We build a table where each cell shows the best value for items up to i and weight w, choosing to include or exclude the current item.

Execution Sample

DSA Typescript

weights = [1, 3, 4]
values = [1, 4, 5]
maxWeight = 7
// dp table rows: items, cols: weights
// Fill dp step by step

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

Execution Table

Step	Item	Weight Capacity w	Include Item Value	Exclude Item Value	Chosen Value	DP Table Row State
1	Item 1 (w=1,v=1)	w=0	N/A (item too heavy)	dp[0][0]=0	0	[0, 0, 0, 0, 0, 0, 0, 0]
2	Item 1 (w=1,v=1)	w=1	1 + dp[0][0]=1	dp[0][1]=0	1	[0, 1, 0, 0, 0, 0, 0, 0]
3	Item 1 (w=1,v=1)	w=2	1 + dp[0][1]=1	dp[0][2]=0	1	[0, 1, 1, 0, 0, 0, 0, 0]
4	Item 1 (w=1,v=1)	w=3	1 + dp[0][2]=1	dp[0][3]=0	1	[0, 1, 1, 1, 0, 0, 0, 0]
5	Item 1 (w=1,v=1)	w=4	1 + dp[0][3]=1	dp[0][4]=0	1	[0, 1, 1, 1, 1, 0, 0, 0]
6	Item 1 (w=1,v=1)	w=5	1 + dp[0][4]=1	dp[0][5]=0	1	[0, 1, 1, 1, 1, 1, 0, 0]
7	Item 1 (w=1,v=1)	w=6	1 + dp[0][5]=1	dp[0][6]=0	1	[0, 1, 1, 1, 1, 1, 1, 0]
8	Item 1 (w=1,v=1)	w=7	1 + dp[0][6]=1	dp[0][7]=0	1	[0, 1, 1, 1, 1, 1, 1, 1]
9	Item 2 (w=3,v=4)	w=0	N/A	dp[1][0]=0	0	[0, 1, 1, 1, 1, 1, 1, 1]
10	Item 2 (w=3,v=4)	w=1	N/A	dp[1][1]=1	1	[0, 1, 1, 1, 1, 1, 1, 1]
11	Item 2 (w=3,v=4)	w=2	N/A	dp[1][2]=1	1	[0, 1, 1, 1, 1, 1, 1, 1]
12	Item 2 (w=3,v=4)	w=3	4 + dp[0][0]=4	dp[0][3]=1	4	[0, 1, 1, 4, 1, 1, 1, 1]
13	Item 2 (w=3,v=4)	w=4	4 + dp[0][1]=5	dp[0][4]=1	5	[0, 1, 1, 4, 5, 1, 1, 1]
14	Item 2 (w=3,v=4)	w=5	4 + dp[0][2]=5	dp[0][5]=1	5	[0, 1, 1, 4, 5, 5, 1, 1]
15	Item 2 (w=3,v=4)	w=6	4 + dp[0][3]=5	dp[0][6]=1	5	[0, 1, 1, 4, 5, 5, 5, 1]
16	Item 2 (w=3,v=4)	w=7	4 + dp[0][4]=6	dp[0][7]=1	6	[0, 1, 1, 4, 5, 5, 5, 6]
17	Item 3 (w=4,v=5)	w=0	N/A	dp[2][0]=0	0	[0, 1, 1, 4, 5, 5, 5, 6]
18	Item 3 (w=4,v=5)	w=1	N/A	dp[2][1]=1	1	[0, 1, 1, 4, 5, 5, 5, 6]
19	Item 3 (w=4,v=5)	w=2	N/A	dp[2][2]=1	1	[0, 1, 1, 4, 5, 5, 5, 6]
20	Item 3 (w=4,v=5)	w=3	N/A	dp[2][3]=4	4	[0, 1, 1, 4, 5, 5, 5, 6]
21	Item 3 (w=4,v=5)	w=4	5 + dp[1][0]=5	dp[1][4]=5	5	[0, 1, 1, 4, 5, 5, 5, 6]
22	Item 3 (w=4,v=5)	w=5	5 + dp[1][1]=6	dp[1][5]=5	6	[0, 1, 1, 4, 5, 6, 5, 6]
23	Item 3 (w=4,v=5)	w=6	5 + dp[1][2]=6	dp[1][6]=5	6	[0, 1, 1, 4, 5, 6, 6, 6]
24	Item 3 (w=4,v=5)	w=7	5 + dp[1][3]=9	dp[1][7]=6	9	[0, 1, 1, 4, 5, 6, 6, 9]

💡 All items and weights processed; final answer dp[3][7] = 9

Variable Tracker

Variable	Start	After Item 1	After Item 2	After Item 3	Final
dp Table Row	[0,0,0,0,0,0,0,0]	[0,1,1,1,1,1,1,1]	[0,1,1,4,5,5,5,6]	[0,1,1,4,5,6,6,9]	[0,1,1,4,5,6,6,9]
Current Item	None	Item 1	Item 2	Item 3	Done
Weight Capacity w	0	0-7	0-7	0-7	7

Key Moments - 3 Insights

Why do we add dp[i-1][w - weight[i]] when including an item?

Because dp[i-1][w - weight[i]] holds the best value without the current item for the remaining weight, so adding current item's value gives total value if included (see steps 12, 13, 22).

Why do we sometimes have 'N/A' for include item value?

When the item's weight is more than current capacity w, it can't fit, so we can't include it (see steps 1, 9, 17).

Why do we choose the max between including and excluding the item?

Because we want the best total value possible for that weight and items considered (see column 'Chosen Value' in execution_table).

Visual Quiz - 3 Questions

Look at the execution table at step 24, what is the chosen value for weight 7 after including item 3?

A 9

B 6

C 5

D 4

💡 Hint

Check the 'Chosen Value' column at step 24 for weight 7.

At which step does the condition 'item fits in weight' become false for item 2?

A Step 9

B Step 12

C Step 10

D Step 11

💡 Hint

Look at steps for item 2 where include value is 'N/A'.

If the weight of item 3 was 5 instead of 4, how would the chosen value at weight 7 change at step 24?

A It would remain 9

B It would decrease

C It would increase

D It would be zero

💡 Hint

Consider if item 3 fits in weight 7 when weight is 5, and check how include value changes.

Concept Snapshot

0 1 Knapsack Problem:
- Use a 2D dp table: rows = items, cols = weights
- dp[i][w] = max value using first i items with capacity w
- For each item and weight:
  Include item if fits: val[i] + dp[i-1][w - weight[i]]
  Exclude item: dp[i-1][w]
- Choose max of include/exclude
- Final answer at dp[last_item][maxWeight]

Full Transcript

The 0 1 Knapsack problem uses a table to find the best value for a given weight limit and items. We fill the table row by row for each item and column by column for each weight capacity. For each cell, we check if the current item fits. If yes, we consider including it by adding its value plus the best value for the remaining weight. We also consider excluding it by taking the previous best value without this item. We pick the maximum of these two. This process repeats until all items and weights are processed. The final answer is in the last cell of the table. This method ensures we consider all combinations without repetition.

Practice

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

easy

A. The minimum weight of items selected

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

C. The number of items selected regardless of weight

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

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 constraint is the maximum weight the knapsack can carry, so total weight must not exceed this limit.

3. Final Answer:

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

4. Quick Check:

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

Hint: Maximize value, not weight, under capacity limit [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Trying to maximize weight instead of value
• Ignoring the weight constraint

2. Which of the following TypeScript function signatures correctly represents the 0 1 Knapsack function?

easy

A. function knapsack(weights: number[], values: number[], capacity: number): number

B. function knapsack(weights: number, values: number, capacity: number[]): number[]

C. function knapsack(weights: string[], values: string[], capacity: string): string

D. function knapsack(weights: number[], values: number[], capacity: string): void

Solution

1. Step 1: Check parameter types

   Weights and values should be arrays of numbers, capacity a number, and return type a number representing max value.

2. Step 2: Match correct signature

   function knapsack(weights: number[], values: number[], capacity: number): number matches this: arrays for weights and values, number for capacity, returns number.

3. Final Answer:

   function knapsack(weights: number[], values: number[], capacity: number): number -> Option A

4. Quick Check:

   Correct types and return = function knapsack(weights: number[], values: number[], capacity: number): number [OK]

Hint: Weights and values are number arrays; capacity is a number [OK]

Common Mistakes:

• Using string types instead of number
• Swapping array and single number types
• Incorrect return type

3. What is the output of the following TypeScript code snippet for 0 1 Knapsack?

const weights = [1, 3, 4];
const values = [15, 50, 60];
const capacity = 5;

function knapsack(w: number[], v: number[], c: number): number {
  const n = w.length;
  const dp = Array(n + 1).fill(null).map(() => Array(c + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= c; j++) {
      if (w[i - 1] <= j) {
        dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][c];
}

console.log(knapsack(weights, values, capacity));

medium

A. 65

B. 60

C. 75

D. 50

Solution

1. Step 1: Understand DP table filling

   For capacity 5, items: (1,15), (3,50), (4,60). Check combinations: - Item1 + Item2: weight 4, value 65 - Item3 alone: weight 4, value 60 - Item2 alone: weight 3, value 50 - Item1 + Item3: weight 5, value 75

2. Step 2: Find max value under capacity

   Item1 + Item3 total weight 5, value 75 is max possible under capacity 5.

3. Final Answer:

   75 -> Option C

4. Quick Check:

   Max value with capacity 5 = 75 [OK]

Hint: Check all item combos fitting capacity, pick max value [OK]

Common Mistakes:

• Ignoring combined items
• Choosing single highest value item only
• Miscomputing weights or values

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

function knapsack(weights: number[], values: number[], capacity: number): number {
  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 = 1; 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];
      }
    }
  }
  return dp[n][capacity];
}

medium

A. Change Array(n + 1).fill([]) to Array(n + 1).fill(null)

B. Change Array(n + 1).fill([]) to Array(n + 1).fill([]).map(() => Array(capacity + 1).fill(0))

C. No bug, code is correct

D. Change Array(n + 1).fill([]) to Array(n + 1).fill(0)

Solution

1. Step 1: Examine the dp array initialization

   The code uses Array(n + 1).fill([]).map(() => Array(capacity + 1).fill(0)), but fill([]) fills all elements with the same array reference, which is then overridden by map creating new arrays. However, the initial fill([]) is unnecessary and can cause confusion or bugs if map is removed.

2. Step 2: Correct initialization

   Better to initialize dp as Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0)) or directly with map to ensure independent arrays without shared references.

3. Final Answer:

   Change Array(n + 1).fill([]) to Array(n + 1).fill([]).map(() => Array(capacity + 1).fill(0)) -> Option B

4. Quick Check:

   Ensure dp rows are independent arrays to avoid shared reference bugs [OK]

Hint: Use map to create independent arrays for dp rows [OK]

Common Mistakes:

• Assuming fill([]) creates independent arrays
• Ignoring shared reference issues
• Claiming no bug when shared references exist

5. Given items with weights [2, 3, 5, 7] and values [10, 5, 15, 7], and a knapsack capacity of 10, which set of items maximizes value without exceeding capacity?

hard

A. Items with weights 2, 3, and 5 (total value 30)

B. Items with weights 3 and 7 (total value 12)

C. Items with weights 5 and 7 (total value 22)

D. Items with weights 2 and 7 (total value 17)

Solution

1. Step 1: Calculate total weights and values for each option

   Items with weights 2, 3, and 5 (total value 30): weights 2+3+5=10, values 10+5+15=30 Items with weights 3 and 7 (total value 12): weights 3+7=10, values 5+7=12 Items with weights 5 and 7 (total value 22): weights 5+7=12 (exceeds capacity) Items with weights 2 and 7 (total value 17): weights 2+7=9, values 10+7=17

2. Step 2: Choose max value under capacity

   Items with weights 2, 3, and 5 (total value 30) fits capacity exactly and has highest value 30.

3. Final Answer:

   Items with weights 2, 3, and 5 (total value 30) -> Option A

4. Quick Check:

   Max value under capacity 10 = 30 [OK]

Hint: Sum weights ≤ capacity; pick max value combo [OK]

Common Mistakes:

• Choosing items exceeding capacity
• Ignoring combined item values
• Selecting fewer items with lower total value