Dynamic Programming — Animate | AI Wisdom

← Back to topic
🎞 ANIMATE · Mode 3 of 5 · +100 XP— Dynamic Programming (Knapsack)
📋Init Table
🔄Fill DP
🤔Decision
🏆Result
🎯 Next: Test →
Step 1 / 4
Speed
Initialise DP table
Create (n+1)×(capacity+1) table filled with zeros💡 Analogy
Draw a spreadsheet with items as rows and weight limits as columns.
Create a 2D table. Rows = items (0 to n), columns = weight limits (0 to capacity). All zeros initially.
Console Output
> 5 rows × 6 columns (capacity=5)
> items: w=[2,3,4,5] v=[3,4,5,6]
> all cells = 0
●knapsack.ts
Initialise DP tableL4–7
1// 0/1 Knapsack — bottom-up DP
2function knapsack(weights: number[], values: number[], capacity: number): number {
3  const n = weights.length;
4  // dp[i][w] = max value using items 0..i with weight capacity w
5  const dp: number[][] = Array.from({length: n + 1}, () =>
6    new Array(capacity + 1).fill(0)
7  );
8 
9  for (let i = 1; i <= n; i++) {
10    for (let w = 0; w <= capacity; w++) {
11      // Option 1: don't take item i
12      dp[i][w] = dp[i-1][w];
13      // Option 2: take item i (if it fits)
14      if (weights[i-1] <= w) {
15        dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
16      }
17    }
18  }
19  return dp[n][capacity];
20}
21 
22const weights = [2, 3, 4, 5];
23const values  = [3, 4, 5, 6];
24knapsack(weights, values, 5); // → 7
24 lines
Timeline — 4 Steps
Initialise DP table
Create (n+1)×(capacity+1) table filled with zeros💡 Analogy
Draw a spreadsheet with items as rows and weight limits as columns.
Create a 2D table. Rows = items (0 to n), columns = weight limits (0 to capacity). All zeros initially.
Console Output
> 5 rows × 6 columns (capacity=5)
> items: w=[2,3,4,5] v=[3,4,5,6]
> all cells = 0

Create (n+1)×(capacity+1) table filled with zeros

Create (n+1)×(capacity+1) table filled with zeros

Was this page helpful?

Discussion

Create (n+1)×(capacity+1) table filled with zeros

Create (n+1)×(capacity+1) table filled with zeros

Was this page helpful?

Discussion