Dynamic Programming
DP State Tables
Watch tabulation fill one state at a time with dependencies, current result, and per-step time and space complexity.
O(items * capacity)
State 0,00
State 0,10
State 0,20
State 0,30
State 0,40
State 0,50
State 0,60
State 0,70
State 0,80
State 1,00
State 1,10
State 1,20
State 1,30
State 1,40
State 1,50
State 1,60
State 1,70
State 1,80
State 2,00
State 2,10
State 2,20
State 2,30
State 2,40
State 2,50
State 2,60
State 2,70
State 2,80
State 3,00
State 3,10
State 3,20
State 3,30
State 3,40
State 3,50
State 3,60
State 3,70
State 3,80
State 4,00
State 4,10
State 4,20
State 4,30
State 4,40
State 4,50
State 4,60
State 4,70
State 4,80
Result
-
Time
O(items * capacity)
Space
O(items * capacity)
Step Note
Solve 0/1 Knapsack for capacity 8.
function knapsack(items: Item[], capacity: number) {
const dp = createTable(items.length + 1, capacity + 1)
for (let item = 1; item <= items.length; item++) {
for (let cap = 0; cap <= capacity; cap++) {
dp[item][cap] = dp[item - 1][cap]
if (items[item - 1].weight <= cap) {
dp[item][cap] = Math.max(dp[item][cap], items[item - 1].value + dp[item - 1][cap - items[item - 1].weight])
}
}
}
return dp[items.length][capacity]
}