How JS uses greedy algorithm to solve the change problem

In real life, we often encounter the problem of making change. Suppose there is an unlimited number of coins with face values ​​of 20,10,5,1. Given the amount of change needed, find the change plan. The requirement is: use the minimum number of coins.

For this kind of problem, the greedy algorithm adopts the method of always selecting the maximum value of coins available for change when changing money. For example, when the number of change required is 25, the change method is 20+5 instead of 10+10+5.

The greedy algorithm is still one of the most common algorithms. This is because it is simple and easy to implement, and it is not very difficult to construct a greedy strategy. In this article, we will share with you an example of JS using greedy algorithm to solve the change problem.

Unfortunately, it needs to be proved before it can be truly applied to the algorithm of the problem.

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

The result is:

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

It should be noted that in some cases, using the greedy algorithm for the change problem cannot obtain the overall optimal solution, and the result may only be a good approximation of the optimal solution.

For example, if the face value of the change provided is 11, 5, 1, the change is 15.

The change method using the greedy algorithm is 11+1+1+1+1, which requires five coins. The optimal solution is 5+5+5, which only requires 3 coins.

Related recommendations:

JS implements the minimum number of change sheets

##code sharing of a small program for change implemented in Python

Two ways to find change

The above is the detailed content of How JS uses greedy algorithm to solve the change problem. For more information, please follow other related articles on the PHP Chinese website!