Greedy Algorithm

贪心算法定义

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择的算法。贪心算法所做出的选择依赖于当前状态，而不依赖于有待于未来的选择。贪心算法对大多数优化问题都能产生整体最优解，但不能保证总是产生最优解。

贪心算法的基本步骤

  1. 建立数学模型来描述问题。
  2. 将求解的问题分成若干个子问题。
  3. 对每个子问题求解，得到子问题的局部最优解。
  4. 将子问题的解局部最优解合成原来问题的一个解。

找零问题

假设商店老板需要找给顾客41分钱的零钱，而他有足够多的25分、10分、5分和1分的硬币。那么如何找零使得找给顾客的硬币个数最少？

function change(money) {
  const coins = [25, 10, 5, 1];
  let result = [];
  for (let coin of coins) {
    while (money >= coin) {
      money -= coin;
      result.push(coin);
    }
  }
  return result;
}


console.log(change(41)); // [25, 10, 5, 1]
console.log(change(43)); // [25, 10, 5, 3]
console.log(change(100)); // [25, 25, 25, 25]
#algorithm

Read Next

Dynamic Programming

Dynamic Programming is a technique used to solve optimization problems by breaking them down into smaller subproblems.

CSS Base

CSS基础知识