Make change using smallest number of coins of given denominations

Question

Given a set of k coins with values v[1], v[2], … v[k] such that v[1] = 1, v[1] < v[2]  < v[3] < v[4] < … < v[k].  We want to make change for a given value n using as few coins as possible.   Present an algorithm to do so.  The algorithm must be optimal in terms of the number of coins.

Answer 1

We use Dynamic Programming

Notation

S(m): Smallest number of coins needed to make change for a value of m

S(1) = 1  // Because v[1] is 1

Recursive Formulation

S(m) = min {1<=i<=k) {S(m-v[i])}  + 1

Optimality

[Argue by contradiction]

Algorithm

S[1]  = 1

for  (m = 2 to n) {

   S[m] = Infinity

   for (coin=1 to k) {

      if (m – v[coin] > 0) {

         temp = S[m – v[coin]] + 1

         S[m] = min{S[m], temp);

      }

   }

}

Time Complexity

O(nk)

Things to think through: Why is this time complexity "exponential"?

Comments

In the line "S[i] = temp;", maybe we should fix it into "S[m] = temp"?

---

@liangyihuang - Yes, absolutely.  Fixed!

Answer 2

Would this be a greedy approach? You are taking the optimum number of higher value coins in each iteration

Notation: 

M = value to make change for

C = the number of coins used

V = coin denominations, V[i] gives the value for i-th coin

     for i = k to 1

          while M >= V[i]

               C += 1

               M -= V[i]

Comments

Yes, this is a greedy approach.  However, it is not optimal in terms of number of coins.  Further, note that you can replace the inner "while" loop with a single line that simply uses remainder and quotient.

---

Unless I'm off base, why is this not optimal? The DP solution looks like it's maximizing lower value coins while this is doing the opposite (which leads to an overall minimization of coins used).

Edit: I see why now, I am falsely assuming "normal" coin values. Greedy would not work in e.g.

V=[1,18,20]
M=36

In greedy, it would be C=17 (20 +. 17 ones), whereas do looks to give 2. I misunderstood the relation.

---

Thats correct!