选择零钱或零钱的硬币 [英] Choosing coins with least or no change given
问题描述
我正在制作一个游戏，游戏币面额为$ 10，$ 5，$ 3和$ 1。玩家的库存中每种类型的货币可能有0或更多，总共最多15个硬币。我试图弄清楚如何正确选择硬币，以使找回的零钱最少。起初我以为这很容易解决，但是现在我束手无策了。
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:
示例1：
用户携带以下硬币：$ 5， 3美元，3美元，3美元，1美元，1美元，1美元，1美元，并想以12美元的价格购买商品。解决方案是用$ 5，$ 3，$ 3，$ 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.
示例2：
用户没有任何$ 1硬币，并且携带$ 5，$ 3，$ 3，$ 3，$ 3。一件商品的价格为12美元，因此他们分别支付了5美元，3美元，3美元和3美元，并返还了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.
由于我们首先选择了较大的硬币，因此我不知道如何知道玩家的库存中是否有足够的价值较低的硬币（在这种情况下为1美元）来容纳示例1，以及是否不足以使用更多的价值较高的硬币（例如本示例） 2。
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:
示例3：
用户拿着以下硬币：$ 5，$ 3，$ 3，$ 3。玩家花了6美元买了东西。最好使用$ 3和$ 3而不返回任何变化，而不是使用$ 5和$ 3并给出$ 2的变化。
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.
对于赏金奖励：
我现在在下面添加了自己的答案作为临时解决方案。但是，我喜欢下面Llama先生的方法（请参阅他引用的链接），并希望找到一个PHP示例来满足此要求。我相信这种方法不需要递归，并且可以使用记忆。
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.
推荐答案
此答案基于גלעד-ברקן的答案。我根据他的要求将其张贴在这里。虽然没有一个答案是我一直在寻找的答案，但我发现这是发布的最佳选择。这是我当前正在使用的修改算法：
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;
}
这是我的测试代码：
$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
当然，时间以微秒为单位，因此执行时间为一秒钟！
Of course that time is in microseconds and therefore it executed in a fraction of a second!
这篇关于选择零钱或零钱的硬币的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
