title: Choosing coins with least or no change given
body: <p>I am making a game which consists of coin denominations of $10, $5, $3, and $1. The player may have 0 or more of each type of currency in his inventory with a maximum of 15 coins in total. I am trying to figure out how to properly select coins so that the least amount of change is given in return. At first I thought this was going to be easy to solve, but now I'm having trouble wrapping my head around it.</p>
  
  <p>Here are two examples that explain the situation further:</p>
  
  <p><strong>Example 1:</strong></p>
  
  <p>The user is carrying these coins: $5, $3, $3, $3, $1, $1, $1, $1 and want to buy an item for $12. The solution would be to pay with $5, $3, $3, $1 and give no change.</p>
  
  <p><strong>Example 2:</strong></p>
  
  <p>The user does not have any $1 coins, and is carrying $5, $3, $3, $3, $3. An item is bought for $12 so they pay with $5, $3, $3, and $3 and change of $2 is given back.</p>
  
  <p>Since we select the larger coins first, what I can't figure out is how to know if there are enough lower valued coins ($1 in this case) in the player's inventory to accommodate example 1, and if there aren't enough to use more of the higher valued coins as in example 2.</p>
  
  <p>A further issue is seen in the following example, though I'd be happy just getting the above two examples working:</p>
  
  <p><strong>Example 3:</strong>
  The user is carrying these coins: $5, $3, $3, $3. The player buys something for $6. It would be better to use $3 and $3 and return no change rather than using $5 and $3 and give $2 in change.</p>
  
  <p>I believe the first two examples can be solved using recursion and a variation of the greedy algorithm.</p>
  
  <p><strong>For the bounty award:</strong></p>
  
  <p>I have added my own answer below as a temporary solution for now. However, I like the approach of Mr. Llama's below (see the link he references) and would like to find a PHP example to satisfy this. I believe this approach does not need recursion and uses memoization.</p>
  
  <p>If there are multiple options for the least amount of change then I would like the tie to be given to the one that pays with the least amount of coins.</p>