Example: Coin Change Minimum Number of coins - rFronteddu/general_wiki GitHub Wiki

Assume to have unlimited coins of different nominations, what is the minimum number of coins to get to a total.

maxCoins(coins, total)
   let d[0..total]
   Arrays.sort(x)
   for i = 1 to total
       r[i] = MAX
       for c : coins // if you wan to know which coins save the index of the coin
           if c > i:
               break;
           q = 1 + d[i - c]
           if q < d[i]
               d[i] = q
   if d[total] == max
        print("Not possible to reach total with coins")
        return
   print("Total: " + d[total]);