贪心算法

贪心算法，又名贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心选择性质
当进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。贪心算法与动态规划的不同之处在于每一次选择是否依赖子问题的解。
最优子结构
一个问题的最优解包括其子问题的最优解。

将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
证明做出贪心选择后，原问题总是存在最优解，即贪心选择是安全的。
证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

渡河问题

4 个人打算渡过一条河，他们只有一条最多能载两个人的船，每个人的划船速度不同，两个人共同划船的速度以慢者为准。他们的划船速度分别为 1，2，5，7 分钟，请设计一个用时最少的渡河方案。
分析
解决渡河问题的核心思想是减少划船时长较长者渡河的次数。
解决方案

拓展后的渡河问题

N 个人打算渡过一条河，他们只有一条最多能载两个人的船，每个人的划船速度不同，两个人共同划船的速度以慢者为准，请设计一个用时最少的渡河方案。
分析
令 T = {t1, t2 , …, tn}为 N 个人的划船时间按升序排列后的集合，Ts 为用时最少的渡河时间，S = {s1, s2 , …, sn}为渡河操作集，sn 为往返一次操作,sn = (ta, tb, tc, tb+tc) (ta < tb)，表示 ta 和 tb 渡河，tc 返回，一次往返时间 ta + tc。

当 N = 1，Ts = T1 = t1；
当 N = 2，Ts = T2 = t1 + t2；
当 N = 3，Ts = T3 = t1 + t2 + t3；
当 N = 4，有两种方案：
- 最快的和次快的渡河，最快的返回；最慢的和次慢的渡河，次慢的返回；最快的和次快的渡河。
  S’= {s1(t1, t2, t1, t1+t2), s2(t3, t4, t2, t2+t4), s3(t1, t2, 0, t2)}
  T4′ = (t1 + t2) + (t2 + t4) + (t2) = t1 + 3 * t2 + t4
- 最快的和最慢的渡河，最快的返回；最快的和次慢的渡河，最快的返回；最快的和次快的渡河。
  S” = {s1(t1, t4, t1, t1+t4), s2(t1, t3, t1, t1+t3), s3(t1, t2, 0, t2)}
  T4″ = (t1 + t4) + (t1 + t3) + (t2) = 2 * t1 + t2 + t3 + t4
- 最少时间方案选择
  ΔT = T4″ – T4′ = t1 + t3 – 2 * t2，Ts = T4 = ΔT > 0 ? T4′ : T4″。

当 N > 4，同 N = 4，可由数学归纳法证明。一般地，将问题简化为：P = {最慢的 tn 和次慢的 tn- 1 渡河用时最少方案}，那么：

SP'= {sp1(t1, t2, t1, t1+t2), sp2(tn-1, tn, t2, t2+tn)}，Ts' = t1 + 2 * t2 + tn；SP" = {s1(t1, tn, t1, t1+tn), s2(t1, tn-1, t1, t1+tn-1)}，Ts" = 2 * t1 + tn-1 + tn；ΔT = Ts"- Ts' = t1 + tn-1 - 2 * t2；SP, Ts = ΔT > 0 ? (SP', Ts'）: (SP", Ts")；TS += Ts, n -= 2, until n < 4。

解决方案
令数组 A[1..n]包含长度为 n 的渡河者划船时间序列，那么：

// 递归
SORT(A)
Ts = 0
CrossRiverGreedy(A, Ts):
    if A.length >= 4:
        Ts' = A[1] + 2 * A[2] + A[n]
        Ts" = 2 * A[1] + A[n-1] + A[n]
        Ts += (Ts"- Ts' > 0) ? Ts': Ts"
        A.length -= 2
        CrossRiverGreedy(A, Ts)
    else
        for i = 1 to A.length:
            Ts += A[i]

// 迭代
SORT(A)
Ts = 0
CrossRiverGreedy(A, Ts):
    i = A.length
    while i >= 4:
        Ts' = A[1] + 2 * A[2] + A[i]
        Ts" = 2 * A[1] + A[i-1] + A[i]
        Ts += (Ts"- Ts' > 0) ? Ts': Ts"
        i -= 2
    while i >= 1:
        Ts += A[i--]

贪心算法的原理

设计贪心算法的步骤

问题

渡河问题

拓展后的渡河问题