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.

Answer 3

I have come up with the following solution. If others can critique it for me I would appreciate it.

<?php

$coin_value = array(10,5,3,1);
$inventory = array(1,2,0,2);
$price = 17;

for ($i = 3; $i >= 0; $i--){

        $btotal = 0;
        $barray = array();

        for ($j = 0; $j < 4; $j++){
                $remaining = $price - $btotal;
                $to_add = floor($remaining / $coin_value[$j]);

                if ($i != 3 && $i == $j){
                        $to_add++;
                }

                if ($inventory[$j] < $to_add){
                        $to_add = $inventory[$j];
                }

                $btotal += $to_add * $coin_value[$j];

                for ($k = 0; $k < $to_add; $k++){
                        $barray[] = $coin_value[$j];
                }

                if ($btotal >= $price)
                        break 2; //warning: breaks out of outer loop

        }
}

$change_due = $btotal - $price;

print_r($barray);

echo "Change due: \$$change_due\n";

?>

It covers examples 1 and 2 in my original question, but does not cover example 3. However, I think it will do for now unless someone can come up with a better solution. I decided not to use recursion as it would seem to take too much time.

Answer 4

You can use a stack to enumerate valid combinations. The version below uses a small optimization, calculating if a minimum of the current denomination is needed. More than one least change combinations are returned if there are any, which could be restricted with memoization; one could also add an early exit if the current denomination could complete the combination with zero change. I hope the laconically commented code is self-explanatory (let me know if you'd like further explanation):

function leastChange($coin_value,$inventory,$price){
  $n = count($inventory);
  $have = 0;
  for ($i=0; $i<$n; $i++){
    $have += $inventory[$i] * $coin_value[$i];
  }

  $stack = [[0,$price,$have,[]]];
  $best = [-max($coin_value),[]];

  while (!empty($stack)){

    // each stack call traverses a different set of parameters
    $parameters = array_pop($stack);
    $i = $parameters[0];
    $owed = $parameters[1];
    $have = $parameters[2];
    $result = $parameters[3];

    // base case
    if ($owed <= 0){
      if ($owed > $best[0]){
        $best = [$owed,$result];
      } else if ($owed == $best[0]){

        // here you can add a test for a smaller number of coins

        $best[] = $result;
      }
      continue;
    }

    // skip if we have none of this coin
    if ($inventory[$i] == 0){
      $result[] = 0;
      $stack[] = [$i + 1,$owed,$have,$result];
      continue;
    }

    // minimum needed of this coin
    $need = $owed - $have + $inventory[$i] * $coin_value[$i];

    if ($need < 0){
      $min = 0;
    } else {
      $min = ceil($need / $coin_value[$i]);
    }

    // add to stack
    for ($j=$min; $j<=$inventory[$i]; $j++){
      $stack[] = [$i + 1,$owed - $j * $coin_value[$i],$have - $inventory[$i] * $coin_value[$i],array_merge($result,[$j])];
      if ($owed - $j * $coin_value[$i] < 0){
        break;
      }
    }
  }

  return $best;
}

Output:

$coin_value = [10,5,3,1];
$inventory = [0,1,3,4];
$price = 12;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,1,2,1],[0,1,1,4],[0,0,3,3]]

$coin_value = [10,5,3,1];
$inventory = [0,1,4,0];
$price = 12;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,0,4]]

$coin_value = [10,5,3,1];
$inventory = [0,1,3,0];
$price = 6;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,0,2]]

$coin_value = [10,5,3,1];
$inventory = [0,1,3,0];
$price = 7;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [-1,[0,1,1]]

Update:

Since you are also interested in the lowest number of coins, I think memoization could only work if we can guarantee that a better possibility won't be skipped. I think this can be done if we conduct our depth-first-search using the most large coins we can first. If we already achieved the same sum using larger coins, there's no point in continuing the current thread. Make sure the input inventory is presenting coins sorted in descending order of denomination size and add/change the following:

// maximum needed of this coin
$max = min($inventory[$i],ceil($owed / $inventory[$i]));

// add to stack 
for ($j=$max; $j>=$min; $j--){

Answer 5

The solution I was able to made covers the 3 examples posted in your question. And always gives the change with as few coins as possible.

The tests I made seemed to be executed very fast.

Here I post the code:

<?php

//Example values
$coin_value = array(10,5,3,1);
$inventory = array(5,4,3,0);
$price = 29;

//Initialize counters
$btotal = 0;
$barray = array(0,0,0,0);

//Get the sum of coins
$total_coins = array_sum($inventory);

function check_availability($i) {
    global $inventory, $barray;
    $a = $inventory[$i];
    $b = $barray[$i];
    $the_diff = $a - $b;
    return $the_diff != 0;
}

/*
 * Checks the lower currency available
 * Returns index for arrays, or -1 if none available
 */
function check_lower_available() {
    for ($i = 3; $i >= 0; $i--) {
        if (check_availability($i)) {
            return $i;
        }
    }
    return -1;
}

for($i=0;$i<4;$i++) {
    while(check_availability($i) && ($btotal + $coin_value[$i]) <= $price) {
        $btotal += $coin_value[$i];
        $barray[$i]++;
    }
}

if($price != $btotal) {
    $buf = check_lower_available();
    for ($i = $buf; $i >= 0; $i--) {
        if (check_availability($i) && ($btotal + $coin_value[$i]) > $price) {
            $btotal += $coin_value[$i];
            $barray[$i]++;
            break;
        }
    }
}

// Time to pay
$bchange = 0;
$barray_change = array(0,0,0,0);

if ($price > $btotal) {
    echo "You have not enough money.";
}
else {
    $pay_msg = "You paid $".$btotal."\n\n";
    $pay_msg.= "You used ".$barray[0]." coins of $10\n";
    $pay_msg.= "You used ".$barray[1]." coins of $5\n";
    $pay_msg.= "You used ".$barray[2]." coins of $3\n";
    $pay_msg.= "You used ".$barray[3]." coins of $1\n\n\n";
    // Time to give change
    $the_diff = $btotal - $price;
    if (!empty($the_diff)) {
        for ($i = 0; $i < 4; $i++) {
            while($the_diff >= $coin_value[$i]) {
                $bchange += $coin_value[$i];
                $barray_change[$i]++;
                $the_diff -= $coin_value[$i];
            }
        }

        $check_sum = array_sum($inventory) - array_sum($barray);
        $check_sum+= array_sum($barray_change);
        $msg = "";
        if ($check_sum < 15) {
            $change_msg = "Your change: $".$bchange."\n\n";
            $change_msg.= "You received ".$barray_change[0]." coins of $10\n";
            $change_msg.= "You received ".$barray_change[1]." coins of $5\n";
            $change_msg.= "You received ".$barray_change[2]." coins of $3\n";
            $change_msg.= "You received ".$barray_change[3]." coins of $1\n\n";
            $msg = $pay_msg.$change_msg;
        }
        else {
            $msg = "You have not enough space to hold the change.\n";
            $msg.= "Buy cancelled.\n";
        }
    }
    else {
        $msg = $pay_msg."You do not need change\n";
    }
    if ($check_sum < 15) {
        for ($i = 0; $i < 4; $i++) {
            $inventory[$i] -= $barray[$i];
            $total_coins-= $barray[$i];
        }
        for ($i = 0; $i < 4; $i++) {
            $inventory[$i] += $barray_change[$i];
            $total_coins+= $barray[$i];
        }
    }
    echo $msg;
    echo "Now you have:\n";
    echo $inventory[0]." coins of $10\n";
    echo $inventory[1]." coins of $5\n";
    echo $inventory[2]." coins of $3\n";
    echo $inventory[3]." coins of $1\n";
}

Answer 6

This is my solution i do not know how efficient is it but it works,i am open for suggestion.

<?php

    $player=array(0,3,1,0);//how much coins you have
    $player_copy=$player;
    $coin_count=array(0,0,0,0);//memorize which coins you gave
    $coin_value=array(1,3,5,10);
    $price=6;       //price of item
    $price_copy=$price;
    $z=3;
    $change=array(-1,-1,-1,-1,-1); //memorise possible changes you can get
    $k=0;
    $flag=0;

label1: for($j=3;$j>=0;$j--){
            $coin_count[$j]=0;
            $player[$j]=$player_copy[$j];
        }
        for($j=$z;$j>=0;$j--){
            while(($price>0) && 1<=$player[$j]){
                $price-=$coin_value[$j];
                $player[$j]--;
                $coin_count[$j]++;
            }
        }
        $change[$k++]=$price;
         if($price!=0){
                for($j=$z;$j>=0;$j--)
                    if($price_copy>$coin_value[$j]){
                        $z=$j-1;
                        $price=$price_copy;
                        goto label1;
                    }
                $flag=1;
         }
    //find minimum change 
        $minv=$change[0];

         for($i=1;$change[$i]>=0 and $i<4;$i++)
             if($change[$i]>$minv)
                $minv=$change[$i];
         $i;
  //when you find minimum change find which coins you have used
         for($i=0;$i<4;$i++)
             if($change[$i]==$minv && $flag==1){
                $flag=2;
                for($j=3;$j>=0;$j--){//reset coin_count and player budget
                    $coin_count[$j]=0;
                    $player[$j]=$player_copy[$j];
                }
                 for($j=3-($i%2)-1;$j>=0;$j--){
                     while(($price>0) && 1<=$player[$j]){
                         $price-=$coin_value[$j];
                         $player[$j]--;
                         $coin_count[$j]++;
                     }
                  }
              }
//prints result
         for($j=0;$j<4;$j++)
            printf("%d x %d\n",$coin_count[$j],$coin_value[$j]);
         printf("change: %d\n",$minv);
?>

Answer 7

I don't know PHP so I've tried it in Java. I hope that is ok as its the algorithm that is important.

My code is as follows:

package stackoverflow.changecalculator;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ChangeCalculator
{
    List<Integer> coinsInTil = new ArrayList<>();

    public void setCoinsInTil(List<Integer> coinsInTil)
    {
        this.coinsInTil = coinsInTil;
    }

    public Map<String, List> getPaymentDetailsFromCoinsAvailable(final int amountOwed, List<Integer> inPocketCoins)
    {
        List<Integer> paid = new ArrayList<>();
        int remaining = amountOwed;

        // Check starting with the largest coin.
        for (Integer coin : inPocketCoins)
            if (remaining > 0 && (remaining - coin) >= 0) {
                    paid.add(coin);
                    remaining = remaining - coin;
            }

        ProcessAlternative processAlternative = new ProcessAlternative(amountOwed, inPocketCoins, paid, remaining).invoke();
        paid = processAlternative.getPaid();
        remaining = processAlternative.getRemaining();

        removeUsedCoinsFromPocket(inPocketCoins, paid);
        int changeOwed = payTheRestWithNonExactAmount(inPocketCoins, paid, remaining);
        List<Integer> change = calculateChangeOwed(changeOwed);

        Map<String, List> result = new HashMap<>();
        result.put("paid", paid);
        result.put("change", change);
        return result;
    }

    private void removeUsedCoinsFromPocket(List<Integer> inPocketCoins, List<Integer> paid)
    {
        for (int i = 0; i < inPocketCoins.size(); i++) {
            Integer coin = inPocketCoins.get(i);
            if (paid.contains(coin))
                inPocketCoins.remove(i);
        }
    }

    private List<Integer> calculateChangeOwed(int changeOwed)
    {
        List<Integer> change = new ArrayList<>();
        if (changeOwed < 0) {
            for (Integer coin : coinsInTil) {
                if (coin + changeOwed == 0) {
                    change.add(coin);
                    changeOwed = changeOwed + coin;
                }
            }
        }
        return change;
    }

    private int payTheRestWithNonExactAmount(List<Integer> inPocketCoins, List<Integer> paid, int remaining)
    {
        if (remaining > 0) {
            for (int coin : inPocketCoins) {
                while (remaining > 0) {
                    paid.add(coin);
                    remaining = remaining - coin;
                }
            }
        }
        return remaining;
    }
}

The ProcessAlternative class handles cases where the largest coin doesn't allow us to get a case where there is no change to be returned so we try an alternative.

package stackoverflow.changecalculator;

import java.util.ArrayList;
import java.util.List;

// if any remaining, check if we can pay with smaller coins first.
class ProcessAlternative
{
    private int amountOwed;
    private List<Integer> inPocketCoins;
    private List<Integer> paid;
    private int remaining;

    public ProcessAlternative(int amountOwed, List<Integer> inPocketCoins, List<Integer> paid, int remaining)
    {
        this.amountOwed = amountOwed;
        this.inPocketCoins = inPocketCoins;
        this.paid = paid;
        this.remaining = remaining;
    }

    public List<Integer> getPaid()
    {
        return paid;
    }

    public int getRemaining()
    {
        return remaining;
    }

    public ProcessAlternative invoke()
    {
        List<Integer> alternative = new ArrayList<>();
        int altRemaining = amountOwed;
        if (remaining > 0) {
            for (Integer coin : inPocketCoins)
                if (altRemaining > 0 && factorsOfAmountOwed(amountOwed).contains(coin)) {
                    alternative.add(coin);
                    altRemaining = altRemaining - coin;
                }
            // if alternative doesn't require change, use it.
            if (altRemaining == 0) {
                paid = alternative;
                remaining = altRemaining;
            }
        }
        return this;
    }

    private ArrayList<Integer> factorsOfAmountOwed(int num)
    {
        ArrayList<Integer> aux = new ArrayList<>();
        for (int i = 1; i <= num / 2; i++)
            if ((num % i) == 0)
                aux.add(i);
        return aux;
    }
}

I worked in it by doing a test for example 1, then for example 2, and lastly moved on to example 3. The process alternative bit was added here and the alternative for the original test coins returned 0 change required so I updated to the amount input to 15 instead of 12 so it would calculate the change required.

Tests are as follows:

package stackoverflow.changecalculator;

import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class ChangeCalculatorTest
{
    public static final int FIFTY_PENCE = 0;
    public static final int TWENTY_PENCE = 1;
    public static final int TEN_PENCE = 2;
    public static final int FIVE_PENCE = 3;
    public static final int TWO_PENCE = 4;
    public static final int PENNY = 5;

    public ChangeCalculator calculator;

    @Before
    public void setUp() throws Exception
    {
        calculator = new ChangeCalculator();
        List<Integer> inTil = new ArrayList<>();
        inTil.add(FIFTY_PENCE);
        inTil.add(TWENTY_PENCE);
        inTil.add(TEN_PENCE);
        inTil.add(FIVE_PENCE);
        inTil.add(TWO_PENCE);
        inTil.add(PENNY);
        calculator.setCoinsInTil(inTil);
    }

    @Test
    public void whenHaveExactAmount_thenNoChange() throws Exception
    {
        // $5, $3, $3, $3, $1, $1, $1, $1
        List<Integer> inPocket = new ArrayList<>();
        inPocket.add(5);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(1);
        inPocket.add(1);
        inPocket.add(1);
        inPocket.add(1);

        Map<String, List> result = calculator.getPaymentDetailsFromCoinsAvailable(12, inPocket);

        List change = result.get("change");
        assertTrue(change.size() == 0);
        List paid = result.get("paid");
        List<Integer> expected = new ArrayList<>();
        expected.add(5);
        expected.add(3);
        expected.add(3);
        expected.add(1);
        assertEquals(expected, paid);
    }

    @Test
    public void whenDoNotHaveExactAmount_thenChangeReturned() throws Exception {
        // $5, $3, $3, $3, $3
        List<Integer> inPocket = new ArrayList<>();
        inPocket.add(5);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);

        Map<String, List> result = calculator.getPaymentDetailsFromCoinsAvailable(15, inPocket);

        List change = result.get("change");
        Object actual = change.get(0);
        assertEquals(2, actual);
        List paid = result.get("paid");
        List<Integer> expected = new ArrayList<>();
        expected.add(5);
        expected.add(3);
        expected.add(3);
        expected.add(3);
        expected.add(3);
        assertEquals(expected, paid);
    }

    @Test
    public void whenWeHaveExactAmountButItDoesNotIncludeBiggestCoin_thenPayWithSmallerCoins() throws Exception {
        // $5, $3, $3, $3
        List<Integer> inPocket = new ArrayList<>();
        inPocket.add(5);
        inPocket.add(3);
        inPocket.add(3);
        inPocket.add(3);

        Map<String, List> result = calculator.getPaymentDetailsFromCoinsAvailable(6, inPocket);

        List change = result.get("change");
        assertTrue(change.size() == 0);
        List paid = result.get("paid");
        List<Integer> expected = new ArrayList<>();
        expected.add(3);
        expected.add(3);
        assertEquals(expected, paid);
    }
}

The tests are not the cleanest yet but they are all passing thus far. I may go back and add some more test cases later to see if I can break it but don't have time right now.

Answer 8

This answer is based off of גלעד-ברקן's answer. I am posting it here as per his request. While none of the answers were quite the one that I was looking for I found that this was the best option posted. Here is the modified algorithm that I am currently using:

<?php

function leastChange($inventory, $price){

    //NOTE: Hard coded these in the function for my purposes, but $coin value can be passed as a parameter for a more general-purpose algorithm
    $num_coin_types = 4;
    $coin_value = [10,5,3,1];

    $have = 0;
    for ($i=0; $i < $num_coin_types; $i++){
            $have += $inventory[$i] * $coin_value[$i];
    }

    //NOTE: Check to see if you have enough money to make this purchase
    if ($price > $have){
            $error = ["error", "Insufficient Funds"];
            return $error;
    }

    $stack = [[0,$price,$have,[]]];
    $best = [-max($coin_value),[]];

    while (!empty($stack)){

            // each stack call traverses a different set of parameters
            $parameters = array_pop($stack);

            $i = $parameters[0];
            $owed = $parameters[1];
            $have = $parameters[2];
            $result = $parameters[3];

            if ($owed <= 0){
                    //NOTE: check for new option with least change OR if same as previous option check which uses the least coins paid
                    if ($owed > $best[0] || ($owed == $best[0] && (array_sum($result) < array_sum($best[1])))){

                            //NOTE: add extra zeros to end if needed
                            while (count($result) < 4){
                                    $result[] = 0;
                            }
                            $best = [$owed,$result];
                    }
                    continue;
            }

            // skip if we have none of this coin
            if ($inventory[$i] == 0){
                    $result[] = 0;
                    $stack[] = [$i + 1,$owed,$have,$result];
                    continue;
            }

            // minimum needed of this coin
            $need = $owed - $have + $inventory[$i] * $coin_value[$i];

            if ($need < 0){
                    $min = 0;
            } else {
                    $min = ceil($need / $coin_value[$i]);
            }

            // add to stack
            for ($j=$min; $j<=$inventory[$i]; $j++){
                    $stack[] = [$i + 1,$owed - $j * $coin_value[$i],$have - $inventory[$i] * $coin_value[$i],array_merge($result,[$j])];
                    if ($owed - $j * $coin_value[$i] < 0){
                            break;
                    }
            }
    }

    return $best;
}

Here is my test code:

$start = microtime(true);

$inventory = [0,1,3,4];
$price = 12;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";



$inventory = [0,1,4,0];
$price = 12;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";

$inventory = [0,1,4,0];
$price = 6;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";


$inventory = [0,1,4,0];
$price = 7;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";


$inventory = [1,3,3,10];
$price=39;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";

$inventory = [1,3,3,10];
$price=45;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";

//stress test
$inventory = [25,25,25,1];
$price=449;
echo "\n";
echo json_encode(leastChange($inventory,$price));
echo "\n";

$time_elapsed = microtime(true) - $start;
echo "\n Time taken: $time_elapsed \n";

The result:

[0,[0,1,2,1]]

[0,[0,0,4,0]]

[0,[0,0,2,0]]

[-1,[0,1,1,0]]

[0,[1,3,3,5]]

["error","Insufficient Funds"]

[-1,[25,25,25,0]]

Time taken: 0.0046839714050293

Of course that time is in microseconds and therefore it executed in a fraction of a second!