Выбор монет с минимальным или никаким изменением

Я делаю игру, состоящую из монетных достоинств в $10, $5, $3 и $1. У игрока может быть 0 или более каждого типа валюты в его инвентаре с максимальным количеством 15 монет. Я пытаюсь понять, как правильно выбрать монеты, чтобы в результате было дано меньшее количество изменений. Сначала я подумал, что это будет легко решить, но теперь у меня проблемы с обволакиванием вокруг него.

Вот два примера, которые объясняют ситуацию далее:

Пример 1:

Пользователь несет эти монеты: $5, $3, $3, $3, $1, $1, $1, $1 и хочет купить товар за $12. Решение было бы заплатить $5, $3, $3, $1 и не давать никаких изменений.

Пример 2:

Пользователь не имеет никаких монет на сумму 1 доллар США и нести $5, $3, $3, $3, $3. Товар куплен за 12 долларов, поэтому они платят с 5, 3, 3 и 3 долларами, и возвращается 2 доллара.

Так как мы сначала выбираем крупные монеты, то я не могу понять, как узнать, есть ли в инвентаре достаточно низкоценных монет (в этом случае 1 доллар США), чтобы разместить пример 1, а если нет достаточно, чтобы использовать более высокоценные монеты, как в примере 2.

Дальнейшая проблема приведена в следующем примере, хотя я был бы рад, если бы вы использовали следующие два примера:

Пример 3: Пользователь несет эти монеты: $5, $3, $3, $3. Игрок покупает что-то за 6 долларов. Лучше использовать $3 и $3 и не возвращать никаких изменений, а не использовать $5 и $3 и давать $2 в изменении.

Я считаю, что первые два примера могут быть решены с помощью рекурсии и вариации жадного алгоритма.

Награда за награду:

Я добавил свой собственный ответ ниже как временное решение. Однако мне нравится подход г-на Лламы ниже (см. Ссылку, на которую он ссылается), и хотел бы найти пример PHP, чтобы удовлетворить это. Я считаю, что этот подход не требует рекурсии и использует memoization.

Если есть несколько вариантов для наименьшего количества изменений, я хотел бы, чтобы связь была привязана к той, которая платит с наименьшим количеством монет.

Ответ 1

Этот ответ основан на ответе גלעד-ברקן. Я отправляю его здесь по его просьбе. Хотя ни один из ответов не был тем, что я искал, я обнаружил, что это лучший вариант. Вот модифицированный алгоритм, который я использую в настоящее время:

<?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;
}

Вот мой тестовый код:

$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";

Результат:

[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

Конечно, это время в микросекундах, и поэтому оно выполняется за долю секунды!

Ответ 2

Проблема может быть определена как:

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

Эта проблема называется проблемой суммы подмножеств. Он NP-полный. Вы не найдете идеальный алгоритм, который работает в псевдополиномиальное время, только несовершенная эвристика.

Однако, если количество монет очень мало, то исчерпывающий поиск пространства решений, безусловно, будет работать.

Если количество монет больше, вы должны посмотреть в Википедию для обзора: https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm

Ответ 3

У меня была аналогичная проблема, за исключением того, что мне разрешалось пройти, комбинация должна была оставаться под целевой суммой. В конце я использовал динамический подход, представленный в этом ответе. Вы также сможете использовать его.

Это выглядит примерно так:

Начните с списка, состоящего из одного пустого элемента.
Для каждой записи в списке...
- Скопируйте запись и добавьте к ней первую монету (не значение монеты!), которую она не содержит.
- Сохраните новый элемент в исходном списке, если и только если * его новое значение суммы еще не существует в списке.
Повторите шаг 2, пока вы не сделаете проход, в который не добавлены новые элементы в список.
Итерируйте список результатов и сохраните лучшую комбинацию (используя ваши критерии).

*: Мы можем сделать эту оптимизацию, потому что мы не особо заботимся о том, какие монеты используются в комбинации, а только суммарное значение коллекции монет.

Вышеуказанный алгоритм может быть оптимизирован бит, если вы используете значение суммы в качестве ключа.

Ответ 4

Я придумал следующее решение. Если другие могут критиковать его за меня, я был бы признателен.

<?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";

?>

Он охватывает примеры 1 и 2 в моем первоначальном вопросе, но не охватывает пример 3. Тем не менее, я думаю, что это будет сделано пока, если кто-то не придумает лучшего решения. Я решил не использовать рекурсию, поскольку, похоже, это займет слишком много времени.

Ответ 5

Вы можете использовать стек для перечисления допустимых комбинаций. В приведенной ниже версии используется небольшая оптимизация, вычисляемая, если требуется минимум текущего номинала. Возвращаются более чем одна комбинация наименьших изменений, если они есть, которые могут быть ограничены записью; можно также добавить ранний выход, если текущее деноминация может завершить комбинацию с нулевым изменением. Я надеюсь, что лаконично прокомментированный код не требует пояснений (дайте мне знать, если вы хотите получить более подробное объяснение):

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;
}

Вывод:

$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:

Поскольку вас также интересует самое низкое количество монет, я думаю, что мемонирование может работать только в том случае, если мы можем гарантировать, что лучшая возможность не будет пропущена. Я думаю, что это можно сделать, если мы проведем наш поиск по глубине с использованием самых больших монет, которые мы можем вначале. Если мы уже достигли той же суммы, используя большие монеты, нет смысла продолжать текущий поток. Убедитесь, что входной инвентарь представляет монеты, отсортированные в порядке убывания размера номинала, и добавьте/измените следующее:

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

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

Ответ 6

Решение, которое я смог сделать, охватывает 3 примера, опубликованные в вашем вопросе. И всегда дает изменение с максимально возможным количеством монет.

Те тесты, которые я сделал, казались выполненными очень быстро.

Здесь я размещаю код:

<?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";
}

Ответ 7

Это мое решение, я не знаю, насколько он эффективен, но он работает, я открыт для предложений.

<?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);
?>

Ответ 8

Я не знаю PHP, поэтому я пробовал его на Java. Я надеюсь, что это нормально, поскольку это важный алгоритм.

Мой код выглядит следующим образом:

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;
    }
}

Класс ProcessAlternative обрабатывает случаи, когда самая крупная монета не позволяет нам получить случай, когда нет изменений для возврата, поэтому мы попробуем альтернативу.

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;
    }
}

Я работал над этим, выполнив тест, например, 1, затем, например, 2, и, наконец, перешел к примеру 3. Альтернативный бит процесса был добавлен здесь, и альтернатива для исходных тестовых монет была возвращена 0, поэтому мне было необходимо обновить к сумме, введенной в 15 вместо 12, чтобы он вычислил требуемое изменение.

Тесты следующие:

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);
    }
}

Тесты не самые чистые, но все они проходят до сих пор. Я могу вернуться и добавить еще несколько тестовых примеров позже, чтобы увидеть, могу ли я сломать его, но у меня нет времени прямо сейчас.