Find the least number of coins required that can make any change from 1 to 99 cents

Question

Recently I challenged my co-worker to write an algorithm to solve this problem      Find the least number of coins required that can make any change from 1 to 99 cents  The coins can only be pennies  1   nickels  5   dimes  10   and quarters  25   and you must be able to make every value from 1 to 99  in 1-cent increments  using those coins    However  I realized that I don t actually know how to do this myself without examining every possible combination of coins  There has to be a better way of solving this problem  but I don t know what the generic name for this type of algorithm would be called  and I can t figure out a way to simplify it beyond looking at every solution   I was wondering if anybody could point me in the right direction  or offer up an algorithm that s more efficient

User · Answer

Came across this one today  while studying https   www coursera org course bioinformatics  DPCHANGE money  coins   MinNumCoins 0    0  for m   1 to money         MinNumCoins m    8         for i   1 to  coins              if m   coini                 if MinNumCoins m - coini    1  lt  MinNumCoins m                      MinNumCoins m    MinNumCoins m - coini    1     output MinNumCoins money    Takes a comma-separated string of denominations available  and the target amount   C  implementation       public static void DPCHANGE int val  string denoms                int   idenoms   Array ConvertAll denoms Split       int Parse           Array Sort idenoms           int   minNumCoins   new int val   1            minNumCoins 0    0          for  int m   1  m  lt   val  m                          minNumCoins m    Int32 MaxValue - 1              for  int i   1  i  lt   idenoms Count   - 1  i                                  if  m  gt   idenoms i                                         if  minNumCoins m - idenoms i     1  lt  minNumCoins m                                                 minNumCoins m    minNumCoins m - idenoms i     1

User · Answer

In general  if you have your coins COIN   and your  change range  1  MAX  the following should find the maximum number of coins   Initialise array CHANGEVAL MAX  to -1  For each element coin in COIN    set CHANGEVAL coin  to 1 Until there are no more -1 in CHANGEVAL    For each index I over CHANGEVAL      if CHANGEVAL I     -1        let coincount   CHANGEVAL I        For each element coin in COIN          let sum   coin   I         if  COINS sum  -1  OR   coincount 1  lt COINS sum              COINS sum  coincount 1   I don t know if the check for coin-minimality in the inner conditional is  strictly speaking  necessary  I would think that the minimal chain of coin-additions would end up being correct  but better safe than sorry

User · Answer

Nice Question  This is the logic I came up with  Tested with few scenarios including 25     class Program          Allowable denominations     const int penny   1      const int nickel   5      const int dime   10      const int quarter   25       const int maxCurrencyLevelForTest  55    1-n where n lt  99      static void Main string   args                         int minPenniesNeeded   0          int minNickelsNeeded   0           int minDimesNeeded   0           int minQuartersNeeded   0            if  maxCurrencyLevelForTest    penny                        minPenniesNeeded   1                    else if  maxCurrencyLevelForTest  lt  nickel                        minPenniesNeeded   MinCountNeeded penny  maxCurrencyLevelForTest                                     else if  maxCurrencyLevelForTest  lt  dime                        minPenniesNeeded   MinCountNeeded penny  nickel - 1               minNickelsNeeded   MinCountNeeded nickel  maxCurrencyLevelForTest                                     else if  maxCurrencyLevelForTest  lt  quarter                        minPenniesNeeded   MinCountNeeded penny  nickel - 1               minNickelsNeeded   MinCountNeeded nickel  dime - 1               minDimesNeeded   MinCountNeeded dime  maxCurrencyLevelForTest                     else                       minPenniesNeeded   MinCountNeeded penny  nickel - 1               minNickelsNeeded   MinCountNeeded nickel  dime - 1               minDimesNeeded   MinCountNeeded dime  quarter - 1                var maxPossilbleValueWithoutQuarters    minPenniesNeeded   penny   minNickelsNeeded   nickel   minDimesNeeded   dime               if  maxCurrencyLevelForTest  gt  maxPossilbleValueWithoutQuarters                                               minQuartersNeeded      maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters -1    quarter    1                                    var minCoinsNeeded   minPenniesNeeded   minNickelsNeeded minDimesNeeded minQuartersNeeded           Console WriteLine String Format  Min Number of coins needed   0    minCoinsNeeded            Console WriteLine String Format  Penny   0  needed   minPenniesNeeded            Console WriteLine String Format  Nickels   0  needed   minNickelsNeeded            Console WriteLine String Format  Dimes   0  needed   minDimesNeeded            Console WriteLine String Format  Quarters   0  needed   minQuartersNeeded            Console ReadLine               private static int MinCountNeeded int denomination  int upperRange                int remainder          return System Math DivRem upperRange  denomination out remainder             Some results   When maxCurrencyLevelForTest   25  Min Number of coins needed  7 Penny  4 needed Nickels  1 needed Dimes  2 needed Quarters  0 needed   When maxCurrencyLevelForTest   99  Min Number of coins needed  10 Penny  4 needed Nickels  1 needed Dimes  2 needed Quarters  3 needed   maxCurrencyLevelForTest   54  Min Number of coins needed  8 Penny  4 needed Nickels  1 needed Dimes  2 needed Quarters  1 needed   maxCurrencyLevelForTest   55  Min Number of coins needed  9 Penny  4 needed Nickels  1 needed Dimes  2 needed Quarters  2 needed   maxCurrencyLevelForTest   79  Min Number of coins needed  9 Penny  4 needed Nickels  1 needed Dimes  2 needed Quarters  2 needed   maxCurrencyLevelForTest   85  Min Number of coins needed  10 Penny  4 needed Nickels  1 needed Dimes  2 needed Quarters  3 needed   The code can further be refactored I guess

User · Answer

Here goes my solution  again in Python and using dynamic programming  First I generate the minimum sequence of coins required for making change for each amount in the range 1  99  and from that result I find the maximum number of coins needed from each denomination   def min any change        V  C    1  5  10  25   99     mxP  mxN  mxD  mxQ   0  0  0  0     solution   min change table V  C      for i in xrange 1  C 1           cP  cN  cD  cQ   0  0  0  0         while i              coin   V solution i               if coin    1                  cP    1             elif coin    5                  cN    1             elif coin    10                  cD    1             else                  cQ    1             i -  coin         if cP  gt  mxP              mxP   cP         if cN  gt  mxN              mxN   cN         if cD  gt  mxD              mxD   cD         if cQ  gt  mxQ              mxQ   cQ     return   pennies  mxP   nickels  mxN   dimes  mxD   quarters  mxQ   def min change table V  C       m  n  minIdx   C 1  len V   0     table  solution    0    m   0    m     for i in xrange 1  m           minNum   float  inf           for j in xrange n               if V j   lt   i and 1   table i - V j    lt  minNum                  minNum   1   table i - V j                   minIdx   j         table i    minNum         solution i    minIdx     return solution   Executing min any change   yields the answer we were looking for    pennies   4   nickels   1   dimes   2   quarters   3   As a test  we can try removing a coin of any denomination and checking if it is still possible to make change for any amount in the range 1  99   from itertools import combinations  def test lst       sums   all sums lst      return all i in sums for i in xrange 1  100    def all sums lst       combs          for i in xrange len lst  1           combs    combinations lst  i      return set sum s  for s in combs    If we test the result obtained above  we get a True   test  1  1  1  1  5  10  10  25  25  25     But if we remove a single coin  no matter what denomination  we ll get a False   test  1  1  1  5  10  10  25  25  25

User · Answer

For this problem  Greedy approach gives a better solution than DP or others   Greedy approach  Find the largest denomination that is lesser than the required value and add it to the set of coins to be delivered  Lower the required cents by the denomination just added and repeat until the required cents becomes zero   My solution  greedy approach  in java solution   public class MinimumCoinDenomination        private static final int   coinsDenominations    1  5  10  25  50  100        public static Map lt Integer  Integer gt  giveCoins int requiredCents            if requiredCents  lt   0                return null                    Map lt Integer  Integer gt  denominations   new HashMap lt Integer  Integer gt              int dollar   requiredCents 100          if dollar gt 0                denominations put 100  dollar                     requiredCents   requiredCents -  dollar   100              int sum   0          while requiredCents  gt  0                for int i   1  i lt coinsDenominations length  i                      if requiredCents  lt  coinsDenominations i                           sum   sum  coinsDenominations i-1                       if denominations containsKey coinsDenominations i-1                              int c   denominations get coinsDenominations i-1                            denominations put coinsDenominations i-1   c 1                         else                           denominations put coinsDenominations i-1   1                                             requiredCents   requiredCents - coinsDenominations i-1                       break                                                    return denominations             public static void main String   args            System out println giveCoins 199

User · Answer

Assuming you re talking about US currency  you would want a Greedy Algorithm  http   en wikipedia org wiki Greedy algorithm  In essence  you try all denominations from highest-to-lowest  taking as many coins as posible from each one until you ve got nothing left   For the general case see http   en wikipedia org wiki Change-making problem  because you would want to use dynamic programming or linear programming to find the answer for arbitrary denominations where a greedy algorithm wouldn t work

User · Answer

After failing to find a good solution to this type of problem in PHP  I developed this function     It takes any amount of money  up to  999 99  and returns an array of the minimum number of each bill   coin required to get to that value   It first converts the value to an int in pennies  for some reason I would get errors at the very end when using standard float values      The returned denominations are also in pennies  ie  5000    50  100    1  etc    function makeChange  val         amountOfMoney   intval  val 100        cashInPennies   array 10000 5000 2000 1000 500 100 25 10 5 1        outputArray   array         currentSum   0       currentDenom   0       while   currentSum  lt   amountOfMoney            if     currentSum    cashInPennies  currentDenom     lt    amountOfMoney                   currentSum    currentSum    cashInPennies  currentDenom                outputArray  cashInPennies  currentDenom                else                currentDenom                         return  outputArray       change   56 93   output   makeChange  change    print r  output   echo   lt br gt Total number of bills  amp  coins    array sum  output        OUTPUT      Array    5000    gt  1  500    gt  1  100    gt  1  25    gt  3  10    gt  1  5    gt  1  1    gt  3    Total number of bills  amp  coins  11

User · Answer

I ve been learning about dynamic programming today  and here s the result   coins    1 5 10 25  d        stores tuples of the form    of coins   coin list      finds the minimum   of coins needed to   make change for some number of cents def m cents       if cents in d keys            return d cents      elif cents  gt  0          choices     m cents - x  0    1  m cents - x  1     x   for x in coins if cents  gt   x             given a list of tuples  python s min function           uses the first element of each tuple for comparison         d cents    min choices          return d cents      else          d 0     0              return d 0   for x in range 1  100       val   m x      print x   cents requires   val 0    coins    val 1    Dynamic programming really is magical

User · Answer

This might be a generic solution in C   using System  using System Collections Generic  using System Linq  using System Text   namespace CoinProblem       class Program               static void Main string   args                        var coins   new int     1  5  10  25       sorted lowest to highest             int upperBound   99              int numCoinsRequired   upperBound   coins Last                for  int i   coins Length - 1  i  gt  0  --i                                numCoinsRequired    coins i    coins i - 1  -  coins i    coins i - 1     0   1   0                             Console WriteLine numCoinsRequired               Console ReadLine                        I haven t fully thought it through   it s too late at night  I thought the answer should be 9 in this case  but Gabe said it should be 10    which is what this yields  I guess it depends how you interpret the question    are we looking for the least number of coins that can produce any value  lt   X  or the least number of coins that can produce any value  lt   X using the least number of coins  For example    I m pretty sure we can make any value with only 9 coins  without nickels  but then to produce 9    you need   oh    I see  You d need 9 pennies  which you don t have  because that s not what we chose    in that case  I think this answer is right  Just a recursive implementation of Thomas  idea  but I don t know why he stopped there   you don t need to brute force anything   Edit  This be wrong

User · Answer

This the code in c  to find the solution   public struct CoinCount       public int coinValue      public int noOfCoins          lt summary gt      Find and returns the no of coins in each coins in coinSet      lt  summary gt       lt param name  coinSet  gt sorted coins value in assending order lt  param gt       lt returns gt  lt  returns gt  public CoinCount   FindCoinsCountFor1to99Collection int   coinSet           Add extra coin value 100 in the coin set  Since it need to find the collection upto 99      CoinCount   result   new CoinCount coinSet Length       List lt int gt  coinValues   new List lt int gt         coinValues AddRange coinSet       coinValues Add 100           Selected coin total values     int totalCount   0      for  int i   0  i  lt  coinValues Count - 1  i                  int count   0          if  totalCount  lt   coinValues i                            Find the coins count             int remainValue   coinValues i   1  - totalCount              count    int Math Ceiling  remainValue   1 0    coinValues i                      else                       if  totalCount  lt   coinValues i   1                   count   1              else                 count   0                    result i    new CoinCount     coinValue    coinValues i   noOfCoins   count            totalCount    coinValues i    count            return result

User · Answer

You can very quickly find an upper bound   Say  you take three quarters  Then you would only have to fill in the  gaps  1-24  26-49  51-74  76-99 with other coins   Trivially  that would work with 2 dimes  1 nickel  and 4 pennies   So  3   4   2   1 should be an upper bound for your number of coins  Whenever your brute-force algorithm goes above thta  you can instantly stop searching any deeper   The rest of the search should perform fast enough for any purpose with dynamic programming    edit  fixed answer as per Gabe s observation

User · Answer

Edit  As the commenters have noted  I have misinterpreted the question   The question is very similar to a basic CS problem I see students at the college having to solve     waves hand This is not the answer you are looking for  That said  while the original answer is wrong  we can use it as a stepping stone to an O n  solution   So  take the wrong answer below  which only solves for a single value  ie  the minimum coinage required for 68 cents  and simply run it for every value   changes      for amount in xrange 1  100      1  99      changes append  run the algo below  amount       Take the maximum for each coin type    ie  if run the algo below returns  q  d  n  p   change    0  0  0  0  for c in changes      change    max c i   change i  for i in xrange 0  4     Now  this will certainly give you a valid answer  but is it a minimal answer   this is the harder part  Currently my gut says yes  but I m still thinking about this one         The wrong answer   Wow  Loops  Dynamic programming  Really folks   In Python   amount     your amount in cents    quarters   amount    25 dimes   amount   25    10 nickels   amount   25   10    5 pennies   amount   25   10   5   Probably some of those modulo operations can be simplified     This isn t hard  you just need to think about how you make change in real life  You give out quarters until adding another quarter would put you over the desired amount  you give out dimes until adding another dime would put you over the desired amount  so on  Then  convert to mathematical operations  modulo and division  Same solution applies for dollars  converting seconds into HH MM SS  etc

User · Answer

import java io IOException  import java io InputStreamReader  import java util Scanner   public class LeastNumofCoins          public int getNumofCoins int amount                        int denominations    50 25 10 5 2 1               int numOfCoins 0              int index 0              while amount gt 0                                int coin denominations index                    if coin  amount                                          numOfCoins                         break                                     if coin lt  amount                                                amount amount-coin                          numOfCoins                                              else                                               index                                                     return numOfCoins            public static void main String   args  throws IOException                   Scanner scanner  new Scanner new InputStreamReader System in              System out println  Enter the Amount               int amoount scanner nextInt              System out println  Number of minimum coins required to make    amoount    is   new LeastNumofCoins   getNumofCoins amoount              scanner close

User · Answer

Solution with greedy approach in java is as below     public class CoinChange       public static void main String args              int denominations      1  5  10  25           System out println  Total required coins are     greeadApproach 53  denominations               public static int greeadApproach int amount  int denominations              int cnt     new int denominations length           for  int i   denominations length-1  amount  gt  0  amp  amp  i  gt   0  i--                cnt i     amount denominations i                amount -  cnt i    denominations i                                 int noOfCoins   0          for  int cntVal   cnt                noOfCoins   cntVal                    return noOfCoins            But this works for single amount  If you want to run it for range  than we have to call it for each amount of range

User · Answer

You need at least 4 pennies  since you want to get 4 as a change  and you can do that only with pennies   It isn t optimal to have more than 4 pennies  Instead of 4 x pennies  you can have 4 pennies and x nickels - they span at least the same range   So you have exactly 4 pennies   You need at least 1 nickel  since you want to get 5 as a change   It isn t optimal to have more than 1 nickel  Instead of 1 x nickels  you can have 1 nickel and x dimes - they span at least the same range   So you have exactly 1 nickel   You need at least 2 dimes  since you want to get 20   This means you have 4 pennies  1 nickel and at least 2 dimes   If you had less than 10 coins  you would have less than 3 quarters  But then the maximal possible change you could get using all coins is 4   5   20   50   79  not enough   This means you have at least 10 coins  Thomas s answer shows that in fact if you have 4 pennies  1 nickel  2 dimes and 3 quarters  all is well

User · Answer

Example Program    include lt stdio h gt         define LEN 9    array length     int main            int coins LEN   0 0 0 0 0 0 0 0 0      coin count         int cointypes LEN   1000 500 100 50 20 10 5 2 1      declare your coins and note here  ASC order             int sum  0    temp variable for sum         int inc 0     for loop         int amount 0     for total amount         printf  Enter Amount              scanf   d   amp amount           while sum lt amount               if  sum cointypes inc   lt  amount                      sum   sum   cointypes inc                         printf   d 1  -  d n  cointypes inc  sum                         switch case to count number of notes and coin                    switch cointypes inc                        case 1000                             coins 0                                break                      case 500                             coins 1                                break                      case 100                             coins 2                                break                      case 50                             coins 3                                break                                     case 20                             coins 4                                 break                      case 10                             coins 5                                break                      case 5                             coins 6                                break                      case 2                             coins 7                                break                      case 1                             coins 8                                break                                            else                     inc                                            printf  note for  d in n note 1000    d n note 500    d n note 100    d n note 50    d n note 20    d n note 10    d n coin 5    d n coin 2    d n coin 1    d n  amount coins 0  coins 1  coins 2  coins 3  coins 4  coins 5  coins 6  coins 7  coins 8

User · Answer

The task  Find the least number of coins required  that can make any change from 1 to 99 cent    differs from the task  For each single change from 1 to 99 cent  find the least number of coins required    because the solution might be a complete different multiset of coins   Suppose you have not  1    5    10   and  25  cent coins  but  1    3    5   and  17  cent coins  To make the change for 5  you only need one  5  coin  but for all changes from 1 to 5 you need two  1  coins and one  3  coin  not any  5  coin   The greedy algorithm iterates from the smallest value to the largest  concerning the change values and coin values   With 1x 1  you get all change values below 2   To make a change of 2  you need an additional coin  which could have any value up to 2  choose greedy - gt  choose the largest - gt   1    With 2x 1  you get all change values below 3   To make a change of 3  you need an additional coin  which could have any value up to 3  choose greedy - gt  choose the largest - gt   3    With 2x 1  1x 3  you get all change values below 6   To make a change of 6  you need an additional coin  which could have any value up to 6  choose greedy - gt  choose the largest - gt   5    and so on      That is in Haskell   coinsforchange  1 3 5 17  99 where     coinsforchange coins change            let f  coinssofar   Int  sumsofar  Int   largestcoin  Int wanttogoto  Int                     let coincount  max 0  wanttogoto-sumsofar largestcoin-1   div largestcoin                  in  replicate coincount largestcoin  coinssofar sumsofar coincount largestcoin           in foldl f     0    zip coins   tail  c-1 c lt -coins      change    And in C     void f std  map lt unsigned int gt   amp coinssofar int  amp sumsofar  unsigned largestcoin  int wanttogoto        int x   wanttogoto - sumsofar   largestcoin - 1      coinssofar largestcoin     x gt 0     x   largestcoin    0        returns coinssofar and sumsofar    std  map lt unsigned int gt  coinsforchange const std  list lt unsigned gt   amp coins  int change        std  map lt unsigned int gt  coinssofar      int sumsofar 0      std  list lt unsigned gt   const iterator coin   coins begin        unsigned largestcoin    coin      for    coin   coin  coins end     largestcoin   coin             f coinssofar sumsofar largestcoin   coin  - 1       f coinssofar sumsofar largestcoin change       return coinssofar

User · Answer

What you are looking for is Dynamic Programming   You don t actually have to enumerate all the possible combinations for every possible values  because you can build it on top of previous answers   You algorithm need to take 2 parameters    The list of possible coin values  here  1  5  10  25  The range to cover  here  1  99    And the goal is to compute the minimal set of coins required for this range   The simplest way is to proceed in a bottom-up fashion   Range     Number of coins  in the minimal set            1   5   10   25  1 1      1  1 2      2  1 3      3  1 4      4  1 5      5  1 5      4   1               two solutions here  1 6      4   1  1 9      4   1  1 10     5   1               experience tells us it s not the most viable one  p  1 10     4   2               not so viable either  1 10     4   1   1  1 11     4   1   1  1 19     4   1   1  1 20     5   1   1           not viable  in the long run   1 20     4   2   1           not viable  in the long run   1 20     4   1   2   It is somewhat easy  at each step we can proceed by adding at most one coin  we just need to know where  This boils down to the fact that the range  x y  is included in  x y 1  thus the minimal set for  x y 1  should include the minimal set for  x y    As you may have noticed though  sometimes there are indecisions  ie multiple sets have the same number of coins  In this case  it can only be decided later on which one should be discarded   It should be possible to improve its running time  when noticing that adding a coin usually allows you to cover a far greater range that the one you added it for  I think   For example  note that     1 5     4 1  1 5   1 9     4 1  1 5   we add a nickel to cover  1 5  but this gives us up to  1 9  for free   However  when dealing with outrageous input sets  2 3 5 10 25  to cover  2 99   I am unsure as how to check quickly the range covered by the new set  or it would be actually more efficient

User · Answer

Here s a simple c  solution using Linq   internal class Program       public static IEnumerable lt Coin gt  Coins   new List lt Coin gt                new Coin  Name    Dime   Value   10           new Coin  Name    Penny   Value   1           new Coin  Name    Nickel   Value   5           new Coin  Name    Quarter   Value   25             private static void Main string   args                PrintChange 34           Console ReadKey              public static void PrintChange int amount                decimal remaining   amount            Order coins by value in descending order         var coinsDescending   Coins OrderByDescending v   gt  v Value           foreach  var coin in coinsDescending                          Continue to smaller coin when current is larger than remainder             if  remaining  lt  coin Value  continue                 Get   of coins that fit in remaining amount             var quotient    int  remaining   coin Value                Console WriteLine new string  -  28                Console WriteLine   0 10  1 15    coin Name  quotient                 Subtract fitting coins from remaining amount             remaining -  quotient   coin Value              if  remaining  lt   0  break    Exit when no remainder left                   Console WriteLine new string  -   28              public class Coin               public string Name   get  set            public int Value   get  set

User · Answer

As I understood if you are using standard currency system values then its super easy to count the minimum number of coins just by a single loop  Just always consume the max coin value and if it not possible check for the next option  But if you have a system like you have coins such as 1 2 3 4 then its not working  I guess the whole idea of having coins as 1 2 5 10 25 is to make computation easy for humans

User · Answer

Here s my take  One Interesting thing is that we need to check min coins needed to form up to coin with max value 25 in our case  - 1 only  After that just calculate the sum of these min coins  From that point we just need to add certain number of coin with max value  to form any number up to the total cost  depending on the difference of total cost and the sum found out  That s it   So for values we have take  once min coins for 24 is found out   1  2  2  5  10  10   We just need to keep adding a 25 coin for every 25 values exceeding 30 sum of min coins   Final answer for 99 is   1  2  2  5  10  10  25  25  25  9  import itertools import math   def ByCurrentCoins val  coins     for i in range 1  len coins    1       combinations   itertools combinations coins  i      for combination in combinations        if sum combination     val          return True    return False  def ExtraCoin val  all coins  curr coins     for c in all coins      if ByCurrentCoins val  curr coins    c          return c  def main      cost   99   coins   sorted  1  2  5  10  25   reverse True    max coin   coins 0     curr coins        for c in range 1  min max coin  cost 1        if ByCurrentCoins c  curr coins         continue      extra coin   ExtraCoin c  coins  curr coins      if not extra coin        print -1       return      curr coins append extra coin     curr sum   sum curr coins    if cost  gt  curr sum      extra max coins   int math ceil  cost - curr sum  float max coin        curr coins extend  max coin for   in range extra max coins       print curr coins   print len curr coins

User · Answer

On the one hand  this has been answered  On the other hand  most of the answers require many lines of code  This Python answer does not require many lines of code  merely many lines of thought        div round up   lambda a  b  a    b if a   b    0 else a    b   1  def optimum change  coins       wallet    0 for i in range 0  len coins  - 1       for j in range 0  len wallet            target   coins j   1  - 1          target -  sum wallet i    coins i  for i in range 0  j           wallet j    max 0  div round up target  coins j        return wallet  optimum change 1  5  10  25  100      4  1  2  3    This is a very simple rescaling algorithm that may perhaps break for inputs which I haven t considered yet  but I think it should be robust  It basically says   to add a new coin type to the wallet  peek at the next coin type N  then add the amount of new coins necessary to make target   N - 1   It calculates that you need at least ceil  target - wallet value  coin value  to do so  and does not check if this will also make every number in between  Notice that the syntax encodes the  from 0 to 99 cents  by appending the final number  100  since that yields the appropriate final target    The reason it does not check is something like   if it can  it automatically will   Put more directly  once you do this step for a penny  value 1   the algorithm can  break  a nickel  value 5  into any subinterval 0 - 4  Once you do it for a nickel  the algorithm can now  break  a dime  value 10   And so on   Of course  it does not require those particular inputs  you can use strange currencies too    gt  gt  gt  optimum change 1  4  7  8  100   3  1  0  12    Notice how it automatically ignores the 7 coin because it knows it can already  break  8 s with the change it has

User · Answer

Inspired from this https   www youtube com watch v GafjS0FfAC0 following 1  optimal sub problem 2  Overlapping sub problem principles introduced in the video  using System  using System Collections Generic  using System Linq   namespace UnitTests moneyChange       public class MoneyChangeCalc               private static int    coinTypes           private Dictionary lt int  int gt   solutions           public MoneyChangeCalc int   coinTypes                         coinTypes   coinTypes              Reset                       public int Minimun int amount                        for  int i   2  i  lt   amount  i                                  IList lt int gt  candidates   FulfillCandidates i                    try                                        solutions Add i  candidates Any      candidates Min     1    0                                     catch  ArgumentException                                        Console WriteLine  key   0      1  already added   i   solutions i                                                 int minimun2               solutions TryGetValue amount  out minimun2                return minimun2                     internal IList lt int gt  FulfillCandidates int amount                        IList lt int gt  candidates   new List lt int gt  3               foreach  int coinType in  coinTypes                                int sub   amount - coinType                  if  sub  lt  0  continue                   int candidate                  if   solutions TryGetValue sub  out candidate                       candidates Add candidate                             return candidates                     private void Reset                          solutions   new Dictionary lt int  int gt                                         0 0     coinTypes 0   1                                         Test cases   using NUnit Framework  using System Collections   namespace UnitTests moneyChange        TestFixture      public class MoneyChangeTest                TestCaseSource  TestCasesData            public int Test minimun2 int amount  int   coinTypes                        var moneyChangeCalc   new MoneyChangeCalc coinTypes               return moneyChangeCalc Minimun amount                      private static IEnumerable TestCasesData                       get                               yield return new TestCaseData 6  new     1  3  4    Returns 2                   yield return new TestCaseData 3  new     2  4  6    Returns 0                   yield return new TestCaseData 10  new     1  3  4    Returns 3                   yield return new TestCaseData 100  new     1  5  10  20    Returns 5

User · Answer

There are a couple of similar answers up there but my solution with Java seems a little easier to understand  Check this out   public static int findMinimumNumberOfCoins int inputCents             Error Check  If the input is 0 or lower  return 0       if inputCents  lt   0  return 0           Create the List of Coins that We need to loop through  Start from highest to lowewst          25-10-5-1      int   mCoinsArray   getCoinsArray             Number of Total Coins       int totalNumberOfCoins   0        for int i 0  i  lt  mCoinsArray length  i                   Get the Coin from Array           int coin   mCoinsArray i                If there is no inputCoin Left  simply break the for-loop          if inputCents    0  break               Check If we have a smaller input than our coin             If it s  we need to go the Next one in our Coins Array              e g  if we have 8  but the current index of array is 10  we need to go to 5           if inputCents  lt  coin  continue            int quotient   inputCents coin           int remainder   inputCents coin               Add qutient to number of total coins           totalNumberOfCoins    quotient               Update the input with Remainder           inputCents   remainder               return totalNumberOfCoins          Create a Coins Array  from 25 to 1  Highest is first   public static int   getCoinsArray           int   mCoinsArray   new int 4        mCoinsArray 0    25       mCoinsArray 1    10       mCoinsArray 2    5       mCoinsArray 3    1        return mCoinsArray

User · Answer

A vb version  Public Class Form1      Private Sub Button1 Click ByVal sender As System Object                                  ByVal e As System EventArgs  Handles Button1 Click         For saleAMT As Decimal   0 01D To 0 99D Step 0 01D             Dim foo As New CashDrawer 0  0  0              Dim chg As List Of Money    foo MakeChange saleAMT  1D              Dim t As Decimal   1 - saleAMT             Debug WriteLine t ToString  C2                For Each c As Money In chg                 Debug WriteLine String Format   0  of  1    c Count ToString  N0    c moneyValue ToString  C2                 Next         Next     End Sub      Class CashDrawer          Private  drawer As List Of Money           Public Sub New Optional ByVal QTYtwoD As Integer   -1                           Optional ByVal QTYoneD As Integer   -1                           Optional ByVal QTYfifty As Integer   -1                           Optional ByVal QTYquarters As Integer   -1                           Optional ByVal QTYdimes As Integer   -1                           Optional ByVal QTYnickels As Integer   -1                           Optional ByVal QTYpennies As Integer   -1               drawer   New List Of Money               drawer Add New Money 2D  QTYtwoD                drawer Add New Money 1D  QTYoneD                drawer Add New Money 0 5D  QTYfifty                drawer Add New Money 0 25D  QTYquarters                drawer Add New Money 0 1D  QTYdimes                drawer Add New Money 0 05D  QTYnickels                drawer Add New Money 0 01D  QTYpennies           End Sub          Public Function MakeChange ByVal SaleAmt As Decimal                                       ByVal amountTendered As Decimal  As List Of Money              Dim change As Decimal   amountTendered - SaleAmt             Dim rv As New List Of Money              For Each c As Money In Me  drawer                 change -   c NumberOf change    c moneyValue                  If c Count  gt  0 Then                     rv Add c                  End If             Next             If change  lt  gt  0D Then Throw New ArithmeticException             Return rv         End Function     End Class      Class Money          -1 equals unlimited qty         Private  qty As Decimal  quantity in drawer         Private  value As Decimal  value money         Private  count As Decimal   0D          Public Sub New ByVal theValue As Decimal                           ByVal theQTY As Decimal              Me  value   theValue             Me  qty   theQTY         End Sub          ReadOnly Property moneyValue As Decimal             Get                 Return Me  value             End Get         End Property          Public Function NumberOf ByVal theAmount As Decimal  As Decimal             If  Me  qty  gt  0 OrElse Me  qty   -1  AndAlso Me  value  lt   theAmount Then                 Dim ct As Decimal   Math Floor theAmount   Me  value                  If Me  qty  lt  gt  -1D Then  qty                       limited qty                     If ct  gt  Me  qty Then  enough                           no                         Me  count   Me  qty                         Me  qty   0D                     Else                          yes                         Me  count   ct                         Me  qty -  ct                     End If                 Else                      unlimited qty                     Me  count   ct                 End If             End If             Return Me  count         End Function          ReadOnly Property Count As Decimal             Get                 Return Me  count             End Get         End Property     End Class End Class

User · Answer

Here s a simple version in Python      usr bin env python  required      coins    25  10  5  1   t      for i in range 1  100       while sum t     i          for c in coins              if sum t    c  lt   i                  t append c                  break     for c in coins          while t count c   gt  required count c               required append c      del t     print required   When run  it prints the following to stdout    1  1  1  1  5  10  10  25  25  25    The code is pretty self-explanatory  thanks Python    but basically the algorithm is to add the largest coin available that doesn t put you over the current total you re shooting for into your temporary list of coins  t in this case   Once you find the most efficient set of coins for a particular total  make sure there are at least that many of each coin in the required list  Do that for every total from 1 to 99 cents  and you re done

User · Answer

I wrote this algorithm for similar kind of problem with DP  may it help  public class MinimumCoinProblem        private static void calculateMinumCoins int   array Coins  int sum             int   array best   new int sum            for  int i   0  i  lt  sum  i                  for  int j   0  j  lt  array Coins length  j                          if  array Coins j   lt   i   amp  amp   array best i     0     array best i - array Coins j     1   lt   array best i                              array best i    array best i - array Coins j     1                                                        System err println  The Value is    array best 14                 public static void main String   args            int   sequence1    11  9 1  3  5 2  20           int sum   30          calculateMinumCoins sequence1  sum

[performance] Find the least number of coins required that can make any change from 1 to 99 cents

Examples related to performance

Examples related to algorithm