贪心算法总是会选择当下的最优解，而不去考虑着一次的选择会不会对未来的选择造成影响。使用贪心算法通常表明，实现者希望做出的这一系列局部的“最优”选择能够带来最终的整体“最优”的选择。如果是这样的话，该算法将会产生一个最优解，否则，则会得到一个次优解。然而，最很多问题来说，寻找最优解很麻烦，这么做不值得，所以使用贪心算法就足够了。

找零问题

贪心算法的典型案例是找零问题。

63 元找零，只有 10元、5元、2元、1元的零钱，如何找零？通过贪心算法必然是：6 张 10 元、1 张 2 元、1 张 1 元。

  1. function makeChange(origAmt, coins) {
  2.   let remainAmt = 0
  3.   if (origAmt % 10 < origAmt) {
  4.     coins[3] = parseInt(origAmt / 10)
  5.     remainAmt = origAmt % 10
  6.     origAmt = remainAmt
  7.   }
  8.   if (origAmt % 5 < origAmt) {
  9.     coins[2] = parseInt(origAmt / 5)
  10.     remainAmt = origAmt % 5
  11.     origAmt = remainAmt
  12.   }
  13.   if (origAmt % 2 < origAmt) {
  14.     coins[1] = parseInt(origAmt / 2)
  15.     remainAmt = origAmt % 2
  16.     origAmt = remainAmt
  17.   }
  19.   coins[0] = parseInt(origAmt / 1)
  20. }

在所有面额都可用且数量不限的情况下，这种方案总能找到最优解。但是如果某种面额的不可用或者数量有限，那么就只能得到一个次优解，也是那种情况下的最优解。

背包问题

如果需要放入背包的物品从本质上是连续的，那么就可以使用贪心算法来解决背包问题。连续的意思是，其可以拆分为很多细小的单位，比如面粉、沙粒等。物品不能是离散的，比如一个人不能进行拆分。当物品是连续的时候，我们可以简单的通过物品的单价除以单位体积来确定物品的价值。

在这种情况下的最优解是，先装价值最高的物品直到物品装完或者将背包装满，接着装价值次之的，以此类推。

解决这种问题的步骤是：

  • 背包容量 W，物品价格 v，重量为 w
  • 计算每种物品的比率 v/w
  • 按比率来降序排列物品
  • 按顺序尽可能多的放入每个物品
  1. function package(values, weights, capacity) {
  2.   let load = 0
  3.   let i = 0
  4.   let w = 0
  6.   while (load < capacity && i < 4) {
  7.     if (weights[i] <= (capacity - load)) {
  8.       w += values[i]
  9.       load += weights[i]
  10.     } else {
  11.       let r = (capacity - load) / weights[i]
  12.       w += r * values[i]
  13.       load += weights[i]
  14.     }
  15.     i++
  16.   }
  17.   return w
  18. }