Suppose you are living in a country where coins have values that are powers of $p$, i.e. $V = [1, 3, 9, 27]$. How do you think the dynamic programming and greedy approaches would compare? Explain.
The dynamic programming (dp) implementation will always yield the optimal solution (minimum number of coins to make change) while the greedy implementation will only produce an optimal solution under certain conditions.
Below are plots comparing the greedy and dp solutions for making change using various values of $p$.
When $p = 3$:
When $p = 4$:
When $p = 5$:
Based on the experimental results above, it seems likely that the greedy solution is equivalent to the optimal solution when the coin denominations are different powers of some integer $p$.
Let's attempt to prove that fact. Consider the case when $V = [p^0] = [1]$. In this case, it's obvious that the greedy solution is equivalent to the optimal solution, since there is only one coin to choose from.
Now consider the case when $V = [p^0, p^1, \ldots, p^k]$ for some $k \geq 1$. If we wish to make change for amount $A$, there are 3 cases to consider:
In the first case, the greedy algorithm will correctly choose the optimal choice of using a single coin. In the second case, we can use the optimal solution from the case with coins $\hat{V} = [p^0, p^1, \ldots, p^{k-1}]$. In the third case, the best we can do is use $p^k$ coins until the point at which we reduce the problem to the second case. The alternative in the third case would be to use $p^n$ coins of denomination $p^{k-n}$ for some $n \leq k$. This is inefficient compared to using a single $p^k$ coin.
These cases will mimic the greedy algorithms logic -- using the highest valued usable coin until the change is made.