Wie JS einen gierigen Algorithmus verwendet, um das Änderungsproblem zu lösen

Im wirklichen Leben stoßen wir häufig auf das Problem, Wechselgeld zu leisten. Angenommen, es gibt eine unbegrenzte Anzahl von Münzen mit den Nennwerten 20, 10, 5 und 1. Finden Sie angesichts der benötigten Wechselgeldmenge den Wechselgeldplan. Die Anforderung lautet: Verwenden Sie die Mindestanzahl an Münzen.

Für diese Art von Problem verwendet der Greedy-Algorithmus die Methode, beim Geldwechsel immer den maximalen Wert der zum Wechseln verfügbaren Münzen auszuwählen. Wenn beispielsweise 25 erforderliche Änderungen erforderlich sind, lautet die Änderungsmethode 20+5 statt 10+10+5.

Der Greedy-Algorithmus ist immer noch einer der am häufigsten verwendeten Algorithmen. Dies liegt daran, dass er einfach und leicht zu implementieren ist und es nicht sehr schwierig ist, eine Greedy-Strategie zu entwickeln. In diesem Artikel zeigen wir Ihnen ein Beispiel dafür, wie JS einen gierigen Algorithmus verwendet, um das Änderungsproblem zu lösen.

Leider muss es bewiesen werden, bevor es wirklich auf den Algorithmus des Problems angewendet werden kann.

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

Das Ergebnis ist:

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

Es ist zu beachten, dass in einigen Fällen die Verwendung des Greedy-Algorithmus für das Änderungsproblem nicht die insgesamt optimale Lösung erhalten kann und das Ergebnis möglicherweise nur eine gute Annäherung an die optimale Lösung ist.

Wenn der Nennwert des bereitgestellten Wechselgelds beispielsweise 11, 5, 1 beträgt, beträgt das Wechselgeld 15.

Die Wechselmethode mit dem Greedy-Algorithmus ist 11+1+1+1+1, wofür fünf Münzen erforderlich sind. Die optimale Lösung ist 5+5+5, wofür nur 3 Münzen erforderlich sind.

Verwandte Empfehlungen:

JS implementiert die Mindestanzahl an Änderungsblättern

Teilen des Codes eines in Python implementierten kleinen Änderungsprogramms

Zwei Möglichkeiten, Veränderung zu finden

Das obige ist der detaillierte Inhalt vonWie JS einen gierigen Algorithmus verwendet, um das Änderungsproblem zu lösen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!