0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Oct 25, 2016 at 8:10
  • $\begingroup$ Related question. $\endgroup$
    – Raphael
    Oct 25, 2016 at 8:11

2 Answers 2

4
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 8, 2018 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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