Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
This is a fairly common problem:
Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible.
Given an input of powers of $p$,
$V = [1, 3, 9, 27]$
How would a dynamic programming vs greedy approach differ in this algorithm? I don't have a good general idea of how these approaches would differ.
A dynamic approach would say that "x$ can be made out of change using, as the first coin, v1 or v2 or v3 ... or vn" and then build a table so that the second coin would be v1 or v2 or v3 ... or vn + one of the precomputed values. Here is a link talking about dynamic: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change
Greedy choice however uses the fact that, for many currencies, we simply can take the maximum value that still gives us less than then our amount and ignore all other possibilities. However, greedy doesn't work for all currencies.
For example: V = {1, 3, 4} and making change for 6: Greedy gives 4 + 1 + 1 = 3 Dynamic gives 3 + 3 = 2
Therefore, greedy algorithms are a subset of dynamic programming. Technically greedy algorithms require optimal substructure AND the greedy choice while dynamic programming only requires optimal substructure.
If $A$ is your amount you're looking for $k_1,\ldots,k_n$ you want to minimize
$$ f(k_1,\dots,k_n) = k_1 + \ldots +k_n $$ subjected to $$ A = k_1 v_1 + \ldots k_n v_n $$
As dynamic programming I would procede as follow... say you want to add $v_i$ to the change, then as next step you will try to minimize the amount the change for the amount $A - v_i$, assuming $A \geq v_i$ of course. So basically for each coin you add the coin to the feasible solution, and recurse for the problem $A - v_i$, once the recursion is over you pick the smallest set of coins. For the greedy solution you iterate from the largest value, keep adding this value to the solution, and then iterate for the next lower coin etc.
I think though you can work out this by simply using divisions. Basically $k_n = \frac{A}{v_n}, k_{n-1} = \frac{A - k_nv_n}{v_{n-1}}, \ldots k_{n-i} = \frac{A - k_n v_n - \ldots k_{n - i + 1} v_{n-i+1}}{v_{n-1}}$ etc... which essentially I think is the solution for the greedy strategy.
