如何证明贪心算法的正确性？

  1. 证明最佳的 solution 可以通过贪心算法在不增加 cost 的情况下求出来
  2. 证明每一步选择时，贪心算法的答案都不劣于其他算法，或者都是最优的

贪心模型

任务规划