JS가 탐욕 알고리즘을 사용하여 변경 문제를 해결하는 방법

실생활에서 우리는 액면가가 20, 10, 5, 1인 동전이 무제한으로 존재하는 경우를 종종 겪게 됩니다. 필요한 변경 금액을 고려하여 변경 계획을 찾으십시오. 요구 사항은 최소 동전 수를 사용하는 것입니다.

이러한 문제에 대해 그리디 알고리즘은 돈을 바꿀 때 항상 바꿀 수 있는 코인의 최대 가치를 선택하는 방식을 채택합니다. 예를 들어, 필요한 변경 횟수가 25인 경우 변경 방법은 10+10+5가 아닌 20+5입니다.

그리디 알고리즘은 여전히 ​​가장 널리 사용되는 알고리즘 중 하나입니다. 이는 간단하고 구현하기 쉽고 그리디 전략을 구성하는 것이 그리 어렵지 않기 때문입니다. 이 글에서는 Greedy 알고리즘을 사용하여 변경 문제를 해결하는 JS의 예를 공유하겠습니다.

안타깝지만 문제의 알고리즘에 실제로 적용하려면 먼저 증명이 필요합니다.

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

결과는 다음과 같습니다.

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

어떤 경우에는 변경 문제에 그리디 알고리즘을 사용하면 전체적인 최적의 솔루션을 얻을 수 없으며 그 결과가 최적의 솔루션에 대한 좋은 근사치일 뿐입니다.

예를 들어 제공된 변화의 액면가가 11, 5, 1이면 변화는 15입니다.

그리디 알고리즘을 사용한 변경 방법은 11+1+1+1+1이며, 5개의 코인이 필요합니다. 최적의 솔루션은 3개의 코인만 필요한 5+5+5입니다.

관련 권장 사항:

JS는 최소 변경 시트 수를 구현합니다

Python으로 구현된 변경을 위한 작은 프로그램 코드

변경 사항을 찾는 두 가지 방법

위 내용은 JS가 탐욕 알고리즘을 사용하여 변경 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!