跳转到内容

贪心

活动选择、Huffman 编码、最小生成树(Kruskal/Prim)、区间调度。本章讲贪心正确性的证明方法(交换论证、拟阵),以及贪心失败的经典反例(0/1 背包、找零)。

  • 贪心必须证明,不能靠感觉
  • 交换论证是最常用的证明技术
  • 拟阵给出贪心成立的一般条件