Choosing coins with least or no change given

Question

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.

Here are two examples that explain the situation further:

Example 1:

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.

Example 2:

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.

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.

A further issue is seen in the following example, though I'd be happy just getting the above two examples working:

Example 3: 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.

I believe the first two examples can be solved using recursion and a variation of the greedy algorithm.

For the bounty award:

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.

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.

Answer 1

The problem can be defined as:

Return a subset of items where the sum is closest to x, but >= x.

This problem is called the subset sum problem. It is NP-complete. You won't find a perfect algorithm that runs in pseudo-polynomial time, only imperfect heuristics.

However, if the number of coins is very small, then an exhaustive search of the solution space will certainly work.

If the number of coins is larger, then you should look at Wikipedia for an overview: https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm

Answer 2

I had a similar problem except instead of being allowed to go over, the combination had to stay under the target amount. In the end, I used the dynamic approach presented in this answer. You should be able to use it too.

It goes something like this:

1. Start with a list consisting of a single empty element.
2. For each entry in the list...
   1. Copy the entry and add to it the first coin (not coin value!) that it doesn't contain.
   2. Store the new element in the original list if and only if* its new sum value doesn't already exist in the list.
3. Repeat step 2 until you make a pass where no new elements are added to the list
4. Iterate the result list and keep the best combination (using your criteria)

*: We can make this optimization because we don't particularly care which coins are used in the combination, only the sum value of the collection of coins.

The above algorithm can be optimized a bit if you use the sum value as the key.