Suppose you have a limited budget for cloud instances. At each step, should you buy the next instance or leave it behind? A state transition formula turns that choice into a lookup in a dynamic-programming table. T[i, j] is the best value available from the first i items with capacity j. The first row and column are zero: no items or no capacity means no value. section 7.1
If item i costs more than j, copy T[i−1, j]. Otherwise, compare skipping it with taking it: T[i, j] = max(T[i−1, j], vᵢ + T[i−1, j−wᵢ]). Here wᵢ is its cost and vᵢ its value. Both lookups use the previous row, so the same item cannot be taken twice. section 7.1
One cell, two choices
For an item costing 2 with value 3, T[2, 3] compares skipping (T[1, 3] = 2) with taking (3 + T[1, 1] = 5). Record 5. section 7.1
Figure 7.3 Visualization of the math used to evaluate cell T[2, 3] (circled in green) on the second row (w2 = 2, v2 = 3). The algorithm resolves a binary choice by executing a maximum value comparison between two paths. The exclusion path inherits the value directly above (T[1, 3] = 2). The active inclusion path accepts the new instance's throughput value (v2 = 3, highlighted in the red solid box) and subtracts its weight from the current capacity (3 - 2 = 1), forcing a pointer lookup to the previous row at column 1 (T[1, 1] = 2, highlighted by the red dotted circle). The combined value of 5 outperforms the exclusion path, updating the cell state.
Follow the two lookups from T[2, 3] to see how the winning value is calculated. section 7.1
