贪心算法

• 定义：总是做出在当前看来最好的选择，不从整体最优考虑。
• 要素：
  1. 贪心选择性质：整体最优解可以通过一系列局部最优的选择达到。
  2. 最优子结构：问题的最优解包含其子问题的最优解。
• 经典案例：
  • 活动安排问题：
    • 策略：总是选择结束时间最早且与已选活动相容的活动。
    • 步骤：将活动按结束时间 $f_i$ 非减序排列，依次选择。
  • 背包问题 (Knapsack)：
    • 区别：如果是0-1背包（物品不可分），贪心法失效。如果是背包问题（物品可分），贪心法有效。
    • 策略：计算 $v_i/w_i$（单位重量价值），优先选性价比高的。