0 votes
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.
in Dynamic Programming by AlgoMeister (1.6k points)

2 Answers

0 votes
 
Best answer

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"?

by AlgoMeister (1.6k points)
In the line "S[i] = temp;", maybe we should fix it into "S[m] = temp"?
@liangyihuang - Yes, absolutely.  Fixed!
0 votes

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]

by Active (340 points)
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!

Related questions

+2 votes
2 answers
asked Mar 3, 2018 in Dynamic Programming by jmlitfi AlgoMeister (684 points)
+1 vote
3 answers
+1 vote
2 answers
+1 vote
3 answers
asked Mar 4, 2018 in Dynamic Programming by jmlitfi AlgoMeister (684 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...