Comment implémenter une solution efficace au problème du moindre changement de pièce en PHP en utilisant l'algorithme glouton ?

Comment implémenter une solution efficace au problème du moindre changement de pièce en PHP en utilisant l'algorithme glouton ?

Citation :
Dans la vie quotidienne, nous avons souvent besoin de faire des changements, notamment lors de nos achats ou de nos échanges commerciaux. Pour utiliser le moins de pièces possible, le montant de la monnaie doit être combiné en utilisant le moins de pièces possible. En programmation informatique, nous pouvons utiliser un algorithme glouton pour résoudre ce problème afin d'obtenir une solution efficace. Cet article décrit comment implémenter une solution efficace au problème de changement minimum de pièces en utilisant l'algorithme glouton de PHP et fournit des exemples de code correspondants.

1. Principe de l'algorithme glouton
   L'algorithme glouton est une idée de résolution de problèmes. Il sélectionne la solution optimale actuelle à chaque étape et obtient finalement la solution optimale globale. Dans le problème du changement minimum de pièces, l'idée de l'algorithme glouton est de sélectionner les pièces dont la plus grande dénomination est inférieure ou égale au montant cible pour effectuer la monnaie à chaque fois jusqu'à ce que toutes les pièces soient trouvées.
2. Solution au problème de changement minimum de pièces
   Voici les étapes pour utiliser l'algorithme glouton pour résoudre le problème de changement minimum de pièces en PHP :

Étape 1 : Créez une fonction nommée minimumCoins qui accepte deux paramètres : montant (montant ) et un tableau de dénominations de pièces (pièces).
Étape 2 : Définissez un tableau de résultats vide (résultat) pour stocker la combinaison de pièces de monnaie.
Étape 3 : Triez le tableau des dénominations des pièces par ordre décroissant pour sélectionner les pièces avec des dénominations plus grandes, de grande à petite.
Étape 4 : Parcourez le tableau des dénominations des pièces et sélectionnez à chaque fois les pièces dont la dénomination actuelle est inférieure ou égale au montant cible pour apporter de la monnaie.
Étape 5 : Pendant le processus de modification, mettez à jour le montant cible, ajoutez la dénomination de pièce sélectionnée au tableau de résultats et soustrayez la dénomination de pièce sélectionnée du montant cible.
Étape 6 : Répétez les étapes 4 et 5 jusqu'à ce que le montant cible soit 0.
Étape 7 : Renvoyez le tableau de résultats.

Ce qui suit est un exemple de code PHP spécifique :

function minimumCoins($amount, $coins) {
    $result = []; // 存储找零的硬币组合
    rsort($coins); // 降序排列硬币面额数组
    
    foreach ($coins as $coin) {
        while ($coin <= $amount) {
            $result[] = $coin; // 将当前硬币面额添加到结果数组中
            $amount -= $coin; // 更新目标金额
        }
    }
    
    return $result;
}

$amount = 47; // 目标金额
$coins = [25, 10, 5, 1]; // 硬币面额数组
$result = minimumCoins($amount, $coins);

echo "找零组合：";
foreach ($result as $coin) {
    echo $coin . " ";
}

Le code ci-dessus affichera : "Changer la combinaison : 25 10 10 1 1", c'est-à-dire que 5 pièces sont nécessaires pour rendre la monnaie de 47 yuans.

3. Complexité temporelle et complexité spatiale
   La complexité temporelle de la résolution du problème de changement minimum de pièces à l'aide de l'algorithme glouton est O(n), où n est le nombre de dénominations de pièces. La complexité spatiale est O(1) car seul un espace supplémentaire constant est requis pour stocker le résultat.

Conclusion :
En utilisant l'algorithme glouton, nous pouvons résoudre efficacement le problème de changement minimum de pièces en PHP. Ce problème est très pratique dans la vie quotidienne, et l’algorithme glouton apporte une solution simple et efficace. J'espère que les exemples de code et les idées de solutions fournis dans cet article vous seront utiles.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!