Comment JS utilise un algorithme glouton pour résoudre le problème du changement

Dans la vraie vie, nous rencontrons souvent le problème de rendre de la monnaie. Supposons qu'il existe un nombre illimité de pièces d'une valeur nominale de 20, 10, 5 et 1. Compte tenu de la quantité de monnaie nécessaire, trouvez le plan de monnaie. La condition est la suivante : utiliser le nombre minimum de pièces.

Pour ce genre de problème, l'algorithme glouton adopte la méthode consistant à toujours sélectionner la valeur maximale des pièces disponibles pour la monnaie lors du changement d'argent. Par exemple, lorsque le nombre de changements requis est de 25, la méthode de changement est 20+5 au lieu de 10+10+5.

L'algorithme glouton reste l'un des algorithmes les plus courants, car il est simple et facile à mettre en œuvre, et il n'est pas très difficile de construire une stratégie glouton. Dans cet article, nous partagerons avec vous un exemple de JS utilisant un algorithme glouton pour résoudre le problème du changement.

Malheureusement, cela doit être prouvé avant de pouvoir être véritablement appliqué à l'algorithme du problème.

<script>
 var money= [20,10,5,1];
 /*
  * m[]:存放可供找零的面值，降序排列
  * n:需要找零数
  */
 function greedyMoney(m,n){
  for(var i=0;i<m.length;i++){
    while(n>=m[i] && n>0){
    document.write(m[i]+" ");
    n = n-m[i];
    }
  }
  document.write("<br>");
  }
  greedyMoney(money,73);
  greedyMoney([25,10,1],63);
</script>

Le résultat est :

20 20 20 10 1 1 1
25 25 10 1 1 1

Il convient de noter que dans certains cas, l'utilisation de l'algorithme glouton pour le problème de changement ne peut pas obtenir la solution optimale globale, et le résultat peut n'être qu'une bonne approximation de la solution optimale.

Par exemple, si la valeur nominale fournie en changement est 11, 5, 1, le changement est 15.

La méthode de changement utilisant l'algorithme glouton est 11+1+1+1+1, ce qui nécessite cinq pièces. La solution optimale est 5+5+5, qui ne nécessite que 3 pièces.

Recommandations associées :

JS implémente le nombre minimum de feuilles de modifications

Partage du code d'un programme de petits changements implémenté en Python

Deux façons de trouver le changement

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!