贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。它不像动态规划算法那样计算更大的格局。
我们来看看如何用贪心算法解决11.2节中的最少硬币找零问题和背包问题。
我们在第9章介绍了一些其他的贪心算法，比如Dijkstra算法、Prim算法和Kruskal算法。
11.3.1 最少硬币找零问题
最少硬币找零问题也能用贪心算法解决。大部分情况下的结果是最优的，不过对有些面额而言，结果不会是最优的。
来看看算法：
function MinCoinChange(coins){ var coins = coins; //{1} this.makeChange = function(amount) { var change = , total = 0; for (var i=coins.length; i>=0; i--){ //{2} var coin = coins[i]; while (total + coin <= amount) { //{3} change.push(coin); //{4} total += coin; //{5} } } return change; };} 不得不说贪心版本的MinCoinChange比动态规划版本的简单多了。和动态规划方法相似，我们传递面额参数，实例化MinCoinChange（行{1}）。
对每个面额（行{2}——从大到小），把它的值和total相加后，total需要小于amount（行{3}）。我们会将当前面额coin添加到结果中（行{4}），也会将它和total相加（行{5}）。
如你所见，这个解法很简单。从最大面额的硬币开始，拿尽可能多的这种硬币找零。当无法再拿更多这种价值的硬币时，开始拿第二大价值的硬币，依次继续。
用和DP方法同样的测试代码测试：
var minCoinChange = new MinCoinChange([1, 5, 10, 25]);console.log(minCoinChange.makeChange(36)); 结果依然是[25, 10, 1]，和用DP得到的一样。下图阐释了算法的执行过程：
然而，如果用[1, 3, 4]面额执行贪心算法，会得到结果[4, 1, 1]。如果用动态规划的解法，会得到最优的结果[3, 3]。
比起动态规划算法而言，贪心算法更简单、更快。然而，如我们所见，它并不总是得到最优答案。但是综合来看，它相对执行时间来说，输出了一个可以接受的解。
11.3.2 分数背包问题
求解分数背包问题的算法与动态规划版本稍有不同。在0-1背包问题中，只能向背包里装入完整的物品，而在分数背包问题中，我们可以装入分数的物品。我们用前面用过的例子来比较两者的差异，如下所示：
物品#
重量
价值
1
2
3
2
3
4
3
4
5
在动态规划的例子里，我们考虑背包能够携带的重量只有5。而在这个例子里，我们可以说最佳解决方案是往背包里装入物品1和物品2，总重量为5，总价值为7。
如果在分数背包问题中考虑相同的容量，得到的结果是一样的。因此，我们考虑容量为6的情况。
在这种情况下，解决方案是装入物品1和物品2，还有25%的物品3。这样，重量为6的物品总价值为8.25。
我们来看看下面这个算法：
function knapSack(capacity, values, weights) { var n = values.length, load = 0, i = 0, val = 0; for (i = 0; i < n && load < capacity; i++) { //{1} if (weights[i] <= (capacity - load)) { //{2} val += values[i]; load += weights[i]; } else { var r = (capacity - load) / weights[i]; //{3} val += r * values[i]; load += weights[i]; } } return w;} 下面是对算法的解释。
行
{1}：总重量少于背包容量，继续迭代，装入物品。行
{2}：如果物品可以完整地装入背包，就将其价值和重量分别计入背包已装入物品的总价值（val）和总重量（load）。行
{3}：如果物品不能完整地装入背包，计算能够装入部分的比例（r）。
如果在0-1背包问题中考虑同样的容量6，我们就会看到，物品1和物品3组成了解决方案。在这种情况下，对同一个问题应用不同的解决方法，会得到两种不同的结果。