= Solution
During the computation in part i, record an index $\operatorname{last}[t]$ attaining the minimum at every positive amount. Starting with $t=v$, print $x_{\operatorname{last}[t]}$ and replace $t$ by $t-x_{\operatorname{last}[t]}$, continuing until $t=0$.
Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to $v$ and their number is exactly $M[v]$, proving optimality. \b[The total <running time> is $O(nv+M[v])$], including the output; $M[v]\le v$ because denomination $1$ is available. The predecessor <array> adds $O(v)$ to the <space complexity>. This is reconstruction from the <dynamic programming> certificate, not the largest-denomination <greedy algorithm>, which need not be optimal for arbitrary denominations.
Back to article page
