当硬币为小数且 returned 数量大于原始 return 值时，查找硬币变化（贪婪算法）

Question

我需要找到给定值的硬币数量，其中硬币是小数位，并且算法可能会 return 更多硬币（钱），因为无法 return returned 数量接近给定值的精确值。

例如：

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”，我正在寻找一种算法来帮助我解决这个问题。我不在乎使用了多少硬币，我只需要确保硬币中的 returned 值与 passed/desired 值一样接近。

有人知道这种情况的解决方案或算法吗？

此致。

Answer 1

贪心算法假定您获得最大可能的硬币，然后是下一个可能的硬币，依此类推，直到达到总和。但它并不能提供一般情况下的最佳解决方案。

因此考虑使用 table 包含可能的总和：

将总和和所有标称值乘以 100 得到整数。

创建长度为 1 + sum + largest_coin 的数组 A[]，用零填充，将 A[0] 设置为 -1。

对于每个面值的硬币 C 遍历数组。如果 A[i-C] 不为零，将值 C 放入 A[i]

在扫描数组范围 A[sum]..A[max] 之后找到第一个非零项。它的索引 K 代表最佳总和。此单元格包含最后添加的硬币 - 因此您可以展开整个组合，一直走到索引 0：A[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

Answer 2

开始使用 我没有足够的声誉在评论中提问我想问你更多的问题但在这里goes.I相信这可以让你开始

-假设我们不确定用户要挑选多少个硬币 -任何硬币都可以与其他硬币数量相同，但必须被视为不同的输入 - 可以将任意数量的硬币加在一起，以便接受最接近所需最大值的总和

脚本到底要实现什么

用户选择随机数量的硬币，然后将其记录下来 array.Any 可以选择并添加随机数量的硬币，如果总和接近特定阈值，则接受这些硬币

概念

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

?>

如果您要解决 refresh.You 的需求，将运行循环执行此操作，直到找到满足您需求的一对

您可以扩展它以检查 3 个随机和 4 个随机等等。

randIndex = array_rand($arrX, 3)...randIndex = array_rand($arrX, 4)....

Php.net 没有说 array_rand 函数不能选择相同的 keys.Personally 从未见过两个选择相同的 time.If 确实发生了。代码应该扩展到记录已经被拾取的硬币，这也应该防止添加硬币反对自己。

这是一个干净的代码...运行任何 return 介于 29 和 35 之间的总和都应该 return 找到。

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

?>

当硬币为小数且 returned 数量大于原始 return 值时，查找硬币变化（贪婪算法）

Find the coin change (Greedy Algorithm) when coins are in decimals and returned amount in coins is larger then original return value

php

algorithm

sorting

coin-change