image.png

    无限循环 + 当前轮的局部最优解

    应用
    找零问题：

    1. /**
    2.  * 找零
    3.  * @param {*} money 需要找的钱
    4.  * @param {*} arr 现有零钱面额合集
    5.  */
    6. function exchange(money, arr) {
    7.   let rst = [],
    8.     len = arr.length
    9.   while (money > 0) {
    10.     let max = 0 // 或者可以等于 -Infinity
    11.     // 找到本轮最大的可用面额
    12.     for (let i = 0; i < len; i++) {
    13.       if(arr[i] > max && arr[i] <= money) { // 这里注意判断条件，可以等于money，寻找最优解的条件必须正确
    14.         max = arr[i]
    15.       }
    16.     }
    17.     rst.push(max) // 把当前轮的最优解记录进去
    18.     money -= max
    19.   }
    20.   return rst
    21. }
    22. let rst = exchange(46, [100, 25, 10, 5, 1])
    23. console.log(rst);