我需要找到达到给定值的硬币数量，其中硬币是小数，并且该算法有可能返回更多硬币（金钱），因为没有办法返回返回金额接近的确切值到给定值。
例如：
Coins: [23, 29.90, 34.50]
Value: 100
可能的解决方案：
Solution 1: 34.60, 34.50, 29.90, 23 (122)
Solution 2: 29.90, 29.90, 29.90 ,29.90 (119.90)
Solution 3: 23, 23, 23, 23, 23 (115)
Solution 4: 23, 23, 23, 34.50 (103.5)
根据可能的解决方案，明显的获胜者是“解决方案 4”，我正在寻找一种算法来帮助我解决这个问题。我不在乎使用了多少硬币，我只需要确保硬币的返回值与通过/期望的值一样接近。
有人知道这种情况的解决方案或算法吗？
贪婪算法假设您获得最大可能的硬币，然后是下一个可能的硬币，依此类推，直到达到总和。但它并不能提供一般情况下的最佳解决方案。
因此考虑使用包含可能总和的表格：
将总和和所有名义值乘以 100 即可得到整数。
制作长度为
A[]1 + sum + largest_coinA[0]-1对于每个标称硬币
CA[i-C]CA[i]扫描完数组范围
A[sum]..A[max]KA[k] => A[k - A[k]]Python代码
def makesum(lst, summ):
mx = max(lst)
A = [-1] + [0]*(mx+summ)
for c in lst:
for i in range(c, summ + c + 1):
if A[i - c]:
A[i] = c
print(A)
#look for the smallest possible combination >= summ
for k in range(summ, summ + mx + 1):
if A[k]:
break
if (k == summ + mx + 1):
return
# unwind combination of used coins
while (k > 0):
print(A[k])
k = k - A[k]
makesum([7, 13, 21], 30)
数组供参考。非零条目 - 可能的总和。
[-1, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 13, 7, 0, 0, 0, 0, 0, 13, 21, 0, 0,
0, 0, 13, 13, 21, 0, 0, 0, 0, 13, 21, 21, 0, 0, 0, 13, 13, 21, 21, 0, 0, 0,
0, 21, 21, 21, 0, 0]
组合：
13
13
7
开始使用 我没有足够的声誉来在评论中询问我想问你更多问题，但就这样了。我相信这可以让你开始
-假设我们不确定用户会选择多少个硬币 -任何硬币的数量可以与其他硬币相同，但必须被视为不同的输入 - 可以将任意数量的硬币加在一起，以便可以接受最接近所需最大值的总和
脚本到底想要实现什么
用户选择随机数量的硬币，记录下来然后放入数组中。可以选择并添加任何随机数量的硬币，如果总和接近特定阈值，则接受这些硬币
概念
<?php
$arrX = array("1.1","20.1","3.5","4","5.7","6.8","7.3","8.6","9","10"); //random coins from user
$minthresh = "30";
$desired = "33";
$maxthresh = "35"; //A threshold is necessary if the desired amount is not enforced
$randIndex = array_rand($arrX, 2); //Pick any random two coins avoid the same coin twice
$sumofpair = $arrX[$randIndex[0]] + $arrX[$randIndex[1]]." Possible acceptable sum<br>"; //Debug to see which two
coins are picked and how much they give
print_r($randIndex[0]);
echo " pair with ";
print_r($randIndex[1]);
echo " = ".$sumofpair; //Debug to see which two coins are picked and how much they give
if (($sumofpair >= "30") && ($sumofpair <= "35")){ //Check if the sum is within the threshold
echo "<br>found something<br>";
echo "<br>This ".$arrX[$randIndex[0]]."+".$arrX[$randIndex[1]]." Gets you this ".$sumofpair." Which is very close to
".$desired;
//if a pair is found show which pair exactly and how much did the pair make
} else { echo "<br>No match so far.Refresh again</br>"; //If the pair do not match refresh until a pair is found...See
below for more info on this }
?>
如果您要解决刷新的需要。您将循环运行此操作，直到找到为您提供所需的对
您可以扩展它来检查 3 个随机和 4 个随机等等。
randIndex = array_rand($arrX, 3)...randIndex = array_rand($arrX, 4)....
Php.net 并没有说 array_rand 函数不能选择相同的键。个人从未见过同时选择两个键。如果确实发生这种情况。 代码应该扩展以记录已经被拾取的硬币，这也应该防止添加针对其自身的硬币。
这是一个干净的代码...运行此任何总和，应返回 29 到 35 之间的返回金额。
<?php
$arrX = array("1.1","20.1","3.5","4","5.7","6.8","7.3","8.6","9","10");
$desired = "32";
$randIndex = array_rand($arrX, 2);
$sumofpair = $arrX[$randIndex[0]] + $arrX[$randIndex[1]];
echo $arrX[$randIndex[0]];
echo " pair with ";
echo $arrX[$randIndex[1]];
echo " = ".$sumofpair;
if (($sumofpair >= "30") && ($sumofpair <= "35")){
echo "<br>This coin ".$arrX[$randIndex[0]]."+ This coin ".$arrX[$randIndex[1]]." = ".$sumofpair." This amount ~ equal
to ".$desired;
} else { echo "<br>Not a match so far.Refresh again</br>"; }
?>