是什么

• 贪心算法： 又称贪婪算法， 期待每一个阶段都是最优， 从而达到全局也是最优，但是结果不一定是最优的
• 回溯算法： 先从一个可能的工作开始解决问题， 如果不行，就回溯并选择另一个动作，直到问题解决

贪心算法

• 示例，兑钱
• 兑换11元 1 元、2 元、5 元的钱币数张，兑换 11 元 贪心算法： 5 + 5 +1 （每一步最优）
• 兑换6元（存在弊端） 1 元、3 元、4 元的钱币数张，兑换 6 元 贪心算法: 4 + 1 +1 (最优 3+3)

回溯算法

result = []
function backtrack(路径, 选择列表):
  if 满足结束条件:
    result.add(路径)
  return
 
  for 选择 of 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

原理

场景