# input:
# - one integer number K
#   (the total amount of change to give back)
# - an array V of values for the various kinds of
#   coints
#
# output:
# - an array N of integers s.t. N[i] = j if
#   I am using j coins of type i
#
# constraint:
# - K = N[1]*V[1] + ... + N[n]*V[n]
#
# goal:
# - minimize  N[1] + ... + N[n]
change_making(K,V) {
   T = NewTable()
   solve(K,V,T)
}

# same input and output as change_making
# but for T which is a Table mapping Ks to
# solutions for the K
solve(K,V,T) {
  if member(K,T) then  // already solved!
     find(K,T)
  else if K = 0 then   // trivial solution
     return [0,...,0]
  else
   Sol = NewStack()   // Sol collects the solutions
                      // to the subproblems,
                      // one for each coin I can
                      // use
   for each c in V do
     if V[c] <= K then
       S = solve(K-V[c],V,T)
       Push((S,c),Sol)
   (Best,c) = ComputeCheapest(Sol)
   Best[c] = Best[c] + 1
   add(K,Best,T)  // remember the solution!
   return Best
}

# Input:
# - stack Sol of pairs (N,c) where N is the
#   vector of coins used in the solution
# Output:
# - returns the pair (N,c) s.t. the vector
#   N is the one of minimal norm in Sol
# Note:
# - the norm of a vector is the sum of the
#   elements in it = the number of coins used
ComputeCheapest(Sol) {
   Min = infinite
   for each (N,c) in Sol {
     if norm(N) < Min then
       Res := (N,C)
   }
   return Res
}


# Complexity analysis:

In the worst case we need to consider K+1
subproblems (for K = 0, 1, 2, .., K)

Table: max size = K
                      AVL
 - member           O(log(K))
 - find             O(log(K))
 - add              O(log(K))

Stack:
 - push O(1)

To summarize:
# the inner for-each loop is executed |V| times
  and each call costs O(1) + the cost of the
  recursive problem
# the cost of ComputeCheapest is again |V|

Finally, the overall cost is:
# O(K * (|V| + log(K)))