Tabulation Bottom Up DP in DSA C - Execution Trace

Concept Flow - Tabulation Bottom Up DP

Initialize DP table with base values

↓

Iterate over items

↓

Iterate over capacities

↓

Compute max value for current cell

↓

Fill DP table row by row

↓

Final answer at DP[last_item

Start by setting base cases in the table, then fill the table row by row using previous results until the final answer is found.

Execution Sample

DSA C

int knapsack(int W, int wt[], int val[], int n) {
  int dp[n+1][W+1];
  for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      if (i == 0 || w == 0) dp[i][w] = 0;
      else if (wt[i-1] <= w) dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
      else dp[i][w] = dp[i-1][w];
    }
  }
  return dp[n][W];
}

This code fills a DP table bottom-up to solve the 0/1 knapsack problem.

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	Condition	DP[i][w] Value	DP Table State
1	Initialize base case	0	0	i==0 or w==0	0	[[0,0,0,0,0,0,0,0]]
2	Initialize base case	0	1	i==0 or w==0	0	[[0,0,0,0,0,0,0,0]]
3	Initialize base case	1	0	i==0 or w==0	0	[[0,0,0,0,0,0,0,0],[0,_,_,_,_,_,_,_]]
4	Check if wt[0] <= w	1	1	wt[0]=1 <= 1	max(val[0]+dp[0][0], dp[0][1])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,_,_,_,_,_,_]]
5	Check if wt[0] <= w	1	2	1 <= 2	max(1+dp[0][1], dp[0][2])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,_,_,_,_,_]]
6	Check if wt[0] <= w	1	3	1 <= 3	max(1+dp[0][2], dp[0][3])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,_,_,_,_]]
7	Check if wt[0] <= w	1	4	1 <= 4	max(1+dp[0][3], dp[0][4])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,_,_,_]]
8	Check if wt[0] <= w	1	5	1 <= 5	max(1+dp[0][4], dp[0][5])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,_,_]]
9	Check if wt[0] <= w	1	6	1 <= 6	max(1+dp[0][5], dp[0][6])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,_]]
10	Check if wt[0] <= w	1	7	1 <= 7	max(1+dp[0][6], dp[0][7])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1]]
11	Check if wt[1] <= w	2	1	wt[1]=3 <= 1? No	dp[1][1]=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,_,_,_,_,_,_]]
12	Check if wt[1] <= w	2	2	3 <= 2? No	dp[1][2]=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,_,_,_,_,_]]
13	Check if wt[1] <= w	2	3	3 <= 3? Yes	max(val[1]+dp[1][0], dp[1][3])=max(4+0,1)=4	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,_,_,_,_]]
14	Check if wt[1] <= w	2	4	3 <= 4? Yes	max(4+dp[1][1], dp[1][4])=max(4+1,1)=5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,_,_,_]]
15	Check if wt[1] <= w	2	5	3 <= 5? Yes	max(4+dp[1][2], dp[1][5])=max(4+1,1)=5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,_,_]]
16	Check if wt[1] <= w	2	6	3 <= 6? Yes	max(4+dp[1][3], dp[1][6])=max(4+1,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,_]]
17	Check if wt[1] <= w	2	7	3 <= 7? Yes	max(4+dp[1][4], dp[1][7])=max(4+1,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]]
18	Check if wt[2] <= w	3	1	wt[2]=4 <= 1? No	dp[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,_,_,_,_,_,_]]
19	Check if wt[2] <= w	3	2	4 <= 2? No	dp[2][2]=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,_,_,_,_,_]]
20	Check if wt[2] <= w	3	3	4 <= 3? No	dp[2][3]=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,_,_,_,_]]
21	Check if wt[2] <= w	3	4	4 <= 4? Yes	max(val[2]+dp[2][0], dp[2][4])=max(5+0,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,_,_,_]]
22	Check if wt[2] <= w	3	5	4 <= 5? Yes	max(5+dp[2][1], dp[2][5])=max(5+1,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,_,_]]
23	Check if wt[2] <= w	3	6	4 <= 6? Yes	max(5+dp[2][2], dp[2][6])=max(5+1,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,_]]
24	Check if wt[2] <= w	3	7	4 <= 7? Yes	max(5+dp[2][3], dp[2][7])=max(5+4,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]]
25	Return final answer	n=3	W=7	dp[3][7]	9	Final max value is 9

💡 All items and capacities processed, final answer at dp[3][7]

Variable Tracker

Variable	Start	After Step 10	After Step 17	After Step 24	Final
i	0	1	2	3	3
w	0	7	7	7	7
dp Table	[[0,...0]]	[[0,...0],[0,1,1,1,1,1,1,1]]	[[0,...0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5]]	[[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,...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]]

Key Moments - 3 Insights

Why do we initialize the first row and first column of the DP table with zeros?

Because when there are zero items (i=0) or zero capacity (w=0), the maximum value achievable is zero. This is shown in execution_table rows 1-3 where dp[i][0] and dp[0][w] are set to 0.

Why do we use dp[i-1][w - wt[i-1]] when including the current item?

Because dp[i-1][w - wt[i-1]] represents the best value achievable with previous items and the reduced capacity after including the current item. This dependency is visible in rows like 4 and 13 where the value is calculated using dp from the previous row.

What happens if the current item's weight is more than the current capacity?

We cannot include the item, so we take the value from the previous row at the same capacity, dp[i-1][w]. This is shown in rows 11 and 12 where wt[1] > w and dp[i][w] = dp[i-1][w].

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the value of dp[2][3]?

A 1

B 4

C 5

D 0

💡 Hint

Refer to execution_table row 13 under 'DP[i][w] Value' column.

At which step does the condition wt[i-1] <= w become false for the first time?

A Step 11

B Step 18

C Step 4

D Step 1

💡 Hint

Check execution_table rows where 'Condition' column shows 'No' for wt[i-1] <= w.

If the weight of the second item (wt[1]) was 2 instead of 3, how would dp[2][3] change at step 13?

A It would remain 4

B It would become 1

C It would become 5

D It would become 0

💡 Hint

Refer to how dp[i][w] is calculated using val[i-1] + dp[i-1][w - wt[i-1]] in execution_table step 13.

Concept Snapshot

Tabulation Bottom Up DP:
- Create a 2D DP table with dimensions (items+1) x (capacity+1)
- Initialize first row and column with 0 (base cases)
- Fill table row-wise: dp[i][w] = max(include current item, exclude current item)
- Include if weight fits: val[i-1] + dp[i-1][w - wt[i-1]]
- Exclude otherwise: dp[i-1][w]
- Final answer at dp[n][W]

Full Transcript

Tabulation Bottom Up Dynamic Programming solves problems by filling a table from the smallest subproblems up to the full problem. We start by initializing the first row and column with zeros because with zero items or zero capacity, no value can be gained. Then, for each item and capacity, we decide whether to include the item if it fits or exclude it otherwise. This decision uses previously computed values in the table. The final answer is found at the bottom-right cell of the table. This method avoids recursion and builds the solution iteratively.