php - 使用最佳面额找零*考虑到使用降序单位可能不会产生正确的结果

Question

我正在努力解决有关编程挑战的问题:

• 规则:
  收银机里只有 2 美元、5 美元和 10 美元的钞票。您的算法应该确定使用尽可能少的钞票进行任意金额找零的最佳方式。

• 测试:
  您的解决方案应包括涵盖示例中提供的场景以及 10 美元、11 美元、21 美元、23 美元和 31 美元具体金额的测试(单元或其他)。

  一些简单的测试输入和预期的优化结果:

  $10: one $10 bill
  $11: one $5, three $2 bills 
  $21: one $10, one $5, three $2 bills
  $23: one $10, one $5, four $2 bills
  $31: two $10, one $5, three $2 bills
  

我的编码尝试有一些缺陷，例如账单数量为非正数、对无法满足的金额的不优雅处理以及 23 美元和 31 美元等金额的错误结果:( Demo )

function rendreMonnaie(int $montant)
{
    //Déclaration des variables
    $listeBillets = [10, 5, 2];  //Liste des coupure dispo
    $nbEntree = 0; //Combien de fois un chiffre entre dans le montant
    $message = [];
    $reste = 0;
    $result = 0;


    for ($ibillet = 0; $ibillet < sizeof($listeBillets); $ibillet++) {
        // Calcul du reste de la division du montant par le billet
        $reste = $montant % $listeBillets[$ibillet];
        if ($reste == 0) {
            // Si le reste est 0, le montant est un multiple du billet
            // Calcul du nombre de billets nécessaires
            $nbEntree = intdiv($montant, $listeBillets[$ibillet]);
            // Ajout du nombre de billets et du type de billet au message
            array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            break;
        } else if ($reste >= $listeBillets[2]) {
            // Si le reste est supérieur ou égal au plus petit billet
            // Calcul du nombre de billets nécessaires
            $nbEntree = intdiv($montant, $listeBillets[$ibillet]);
            // Ajout du nombre de billets et du type de billet au message
            array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            // Mise à jour du montant avec le reste
            $montant = $reste;
        } else {
            if ($listeBillets[$ibillet] == 2) { 
               $nbEntree = intdiv($result, $listeBillets[$ibillet]);
               array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            } else {
                $result = $montant - $listeBillets[$ibillet];
                $reste = $reste % $listeBillets[$ibillet];
                // Calcul du nombre de billets nécessaires
                $nbEntree = intdiv($result, $listeBillets[$ibillet]);
                array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            }
        }
    }
    // Affichage du tableau message pour le débogag
    for ($i = 0; $i < sizeof($message); $i++) {
        // Suppression des éléments du message qui commencent par un nombre inférieur à 1
        if ($message[$i][0] < 1) {
            unset($message[$i]);
        }
    }
    // Conversion du tableau message en une chaîne de caractères
    $message = implode(" + ", $message);
    echo ($message);
}

Answer 1

我想出了一个解决方案，但它绝不是最佳的(特别是当目标数量变得相当大时)。首先，让我们定义一个类，其中包含多个面额的集合，这些面额可能包含问题的解决方案。

class ChangeCollection
{
    public function __construct(protected array $denominations = [])
    {
    }

    public function getTotal()
    {
        return array_sum($this->denominations);
    }

    public function getDenominationsString()
    {
        sort($this->denominations);
        return implode(' ', $this->denominations);
    }

    public function addDenominations(array $denominations): array
    {
        return array_map(
            fn (int $denomination) => new ChangeCollection([...$this->denominations, $denomination]),
            $denominations
        );
    }
}

现在，我们定义一个类，它实际上构建 ChangeCollection 对象的组合，并检查它是否包含实际的解决方案。

class ChangeCalculator
{
    protected const DENOMINATIONS = [2, 5, 10];

    public function calculate(int $target): ChangeCollection
    {
        $collections = [new ChangeCollection];
        do {
            $collections = array_filter(array_merge(...array_map(
                fn (ChangeCollection $collection) => $collection->addDenominations(self::DENOMINATIONS),
                $collections
            )), fn (ChangeCollection $collection) => $collection->getTotal() <= $target);

            foreach ($collections as $collection) {
                if ($collection->getTotal() === $target) {
                    return $collection;
                }
            }
        } while (count($collections) > 0);

        throw new Exception("There is no possible combination of denominations.");
    }
}

您现在可以使用以下代码获取带有结果的字符串:

$calculator = new ChangeCalculator;
echo $calculator->calculate(23)->getDenominationsString();