选择最少或没有变化的硬币

Question

我制作的游戏包括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美元的变化.

我相信前两个例子可以使用递归和贪婪算法的变体来解决.

赏金奖励:

我现在已经在下面添加了我自己的答案作为临时解决方案.但是,我喜欢Llama先生的方法(参见他引用的链接),并希望找到一个PHP示例来满足这一要求.我相信这种方法不需要递归并使用memoization.

如果有多个选项可以进行最少量的更改,那么我希望能够以最少的硬币付款.

Answer 1

问题可以定义为:

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

Answer 2

我有类似的问题,除了被允许过去,组合必须保持在目标金额之下.最后,我使用了这个答案中提出的动态方法.你也应该能够使用它.

它是这样的:

1. 从包含单个空元素的列表开始.
2. 对于列表中的每个条目......
   1. 复制该条目并添加它不包含的第一个硬币(不是硬币值!).
   2. 当且仅当*新的总和值不存在于列表中时,将新元素存储在原始列表中.
3. 重复步骤2,直到您创建一个没有新元素添加到列表的过程
4. 迭代结果列表并保持最佳组合(使用您的标准)

*:我们可以进行优化,因为我们并不特别关心组合中使用哪些硬币,只是硬币集合的总和值.

如果使用和值作为关键字,可以稍微优化上述算法.

Answer 3

这个答案基于 \xd7\x92\xd7\x9c\xd7\xa2\xd7\x93-\xd7\x91\xd7\xa8\xd7\xa7\xd7\x9f\ 的答案。我根据他的要求将其发布在这里。虽然没有一个答案完全是我正在寻找的答案，但我发现这是发布的最佳选项。这是我目前使用的修改后的算法：

\n\n

<?php\n\nfunction leastChange($inventory, $price){\n\n    //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\n    $num_coin_types = 4;\n    $coin_value = [10,5,3,1];\n\n    $have = 0;\n    for ($i=0; $i < $num_coin_types; $i++){\n            $have += $inventory[$i] * $coin_value[$i];\n    }\n\n    //NOTE: Check to see if you have enough money to make this purchase\n    if ($price > $have){\n            $error = ["error", "Insufficient Funds"];\n            return $error;\n    }\n\n    $stack = [[0,$price,$have,[]]];\n    $best = [-max($coin_value),[]];\n\n    while (!empty($stack)){\n\n            // each stack call traverses a different set of parameters\n            $parameters = array_pop($stack);\n\n            $i = $parameters[0];\n            $owed = $parameters[1];\n            $have = $parameters[2];\n            $result = $parameters[3];\n\n            if ($owed <= 0){\n                    //NOTE: check for new option with least change OR if same as previous option check which uses the least coins paid\n                    if ($owed > $best[0] || ($owed == $best[0] && (array_sum($result) < array_sum($best[1])))){\n\n                            //NOTE: add extra zeros to end if needed\n                            while (count($result) < 4){\n                                    $result[] = 0;\n                            }\n                            $best = [$owed,$result];\n                    }\n                    continue;\n            }\n\n            // skip if we have none of this coin\n            if ($inventory[$i] == 0){\n                    $result[] = 0;\n                    $stack[] = [$i + 1,$owed,$have,$result];\n                    continue;\n            }\n\n            // minimum needed of this coin\n            $need = $owed - $have + $inventory[$i] * $coin_value[$i];\n\n            if ($need < 0){\n                    $min = 0;\n            } else {\n                    $min = ceil($need / $coin_value[$i]);\n            }\n\n            // add to stack\n            for ($j=$min; $j<=$inventory[$i]; $j++){\n                    $stack[] = [$i + 1,$owed - $j * $coin_value[$i],$have - $inventory[$i] * $coin_value[$i],array_merge($result,[$j])];\n                    if ($owed - $j * $coin_value[$i] < 0){\n                            break;\n                    }\n            }\n    }\n\n    return $best;\n}\n

\n\n

这是我的测试代码：

\n\n

$start = microtime(true);\n\n$inventory = [0,1,3,4];\n$price = 12;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n\n\n$inventory = [0,1,4,0];\n$price = 12;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n$inventory = [0,1,4,0];\n$price = 6;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n\n$inventory = [0,1,4,0];\n$price = 7;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n\n$inventory = [1,3,3,10];\n$price=39;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n$inventory = [1,3,3,10];\n$price=45;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n//stress test\n$inventory = [25,25,25,1];\n$price=449;\necho "\\n";\necho json_encode(leastChange($inventory,$price));\necho "\\n";\n\n$time_elapsed = microtime(true) - $start;\necho "\\n Time taken: $time_elapsed \\n";\n

\n\n

结果：

\n\n

[0,[0,1,2,1]]\n\n[0,[0,0,4,0]]\n\n[0,[0,0,2,0]]\n\n[-1,[0,1,1,0]]\n\n[0,[1,3,3,5]]\n\n["error","Insufficient Funds"]\n\n[-1,[25,25,25,0]]\n\nTime taken: 0.0046839714050293\n

\n\n

当然，该时间以微秒为单位，因此它在不到一秒的时间内执行！

\n