Выбор монет с минимальным или никаким изменением
Я делаю игру, состоящую из монетных достоинств в $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);
}
}
Тесты не самые чистые, но все они проходят до сих пор. Я могу вернуться и добавить еще несколько тестовых примеров позже, чтобы увидеть, могу ли я сломать его, но у меня нет времени прямо сейчас.
