Lesson 2

Often we want not only the value of the best error, but also the share vector that achieves it. During the dynamic program, remember which number of shares \(a\) gave the best transition into each state \((i,b)\). After the table is filled, choose a spent amount \(b\) with minimum \(D_{n}(b)\) and walk backward: \[a_{i}=\operatorname{choice}(i,b),\qquad b\leftarrow b-p_{i} a_{i}.\] Repeating this for \(i=n,n-1,\dotsc,1\) restores one optimal vector.