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.

  • 1
    What research have you done? This is a well-known problem, algorithms for which are available from many sources. At the very least, you should try to apply these algorithms to some example inputs. – Raphael Oct 25 '16 at 8:10
  • Related question. – Raphael Oct 25 '16 at 8:11
up vote 1 down vote accepted

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.

  • I think the question here is, for which cases greedy works and which cases it doesn't work. – orezvani Oct 25 '16 at 4:41
  • This paper describes an algorithm for checking whether a coin set can be used for the greedy algorithm. – adrianN Oct 25 '16 at 8:40

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.

  • Of course in my discussion for the dynamic programming part I didn't mention how you would avoid to solve subproblems already solved, but that's an easy fix using memoization. – user8469759 Mar 8 at 17:19

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.