贪心算法遵循一种近似解决问题的技术,期盼通过每个阶段的局部最优选择(当前最好的解),从而达到全局的最优(全局最优解)。它不像动态规划算法那样计算更大的格局
特点:比起动态规划算法而言,贪心算法更简单、更快。然而它并不总是能得到最优答案
例子
最少硬币找零问题:
1 | function minCoinChange(coins, amount) { |
分数背包问题:
(在0-1背包问题中,只能向背包里装入完整的物品,而在分数背包问题中,可以装入分数的物品)
1 | function knapSack(capacity, weights, values) { |