贪心算法

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

贪心算法的原理

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

设计贪心算法的步骤

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

问题

渡河问题

4个人打算渡过一条河,他们只有一条最多能载两个人的船,每个人的划船速度不同,两个人共同划船的速度以慢者为准。他们的划船速度分别为1,2,5,7分钟,请设计一个用时最少的渡河方案。

分析
解决渡河问题的核心思想是减少划船时长较长者渡河的次数。

解决方案
crossriver

拓展后的渡河问题

N个人打算渡过一条河,他们只有一条最多能载两个人的船,每个人的划船速度不同,两个人共同划船的速度以慢者为准,请设计一个用时最少的渡河方案。

分析
令用时最少的渡河时间为Ts,N个人的划船时间按升序排列后的集合为:

$$ T = \{t_1, t_2, ..., t_n\}; $$

渡河操作集为:

$$ S = \{s_1, s_2 , ..., s_n\}; $$

往返一次操作为:

$$ s_n = (<t_a, t_b>, t_a, t_a + t_b),(t_a < t_b)。 $$

$$ (s_n即表示t_a和t_b渡河,t_a返回,一次往返时间 t_a + t_b。) $$

  1. 当N = 1
    $$ Ts = T_1 = t_1 $$
  2. 当N = 2
    $$ Ts = T_2 = t_1 + t_2 $$
  3. 当N = 3
    $$ Ts = T_3 = t_1 + t_2 + t_3$$
  4. 当N = 4,有两种方案:

    • 方案1 最快的和次快的渡河,最快的返回;最慢的和次慢的渡河,次慢的返回;最快的和次快的渡河,结束。

      $$ S'= {s_1(<t_1, t_2>, t_1, t_1+t_2), s_2(<t_3, t_4>, t_2, t_2+t_4), s_3(<t_1, t_2>, null, t_2)} $$

      $$ T_4' = (t_1 + t_2) + (t_2 + t_4) + (t_2) = t_1 + 3t_2 + t_4 $$

    • 方案2 最快的和最慢的渡河,最快的返回;最快的和次慢的渡河,最快的返回;最快的和次快的渡河,结束。

      $$ S'' = {s_1(<t_1, t_4>, t_1, t_1+t_4), s_2(<t_1, t_3>, t_1, t_1+t_3), s_3(<t_1, t_2>, null, t_2)} $$

      $$ T_4''= (t_1 + t_4) + (t_1 + t_3) + (t_2) = 2t_1 + t_2 + t_3 + t_4 $$

    • 从以上两种方案中选择用时最少的方案

      $$ \Delta T = T_4'' - T_4' =(2t_1 + t_2 + t_3 + t_4) - (t_1 + 3t_2 + t_4)= t_1 + t_3 - 2t_2 $$

      $$ Ts = T_4 = \Delta T > 0 ? T_4' : T_4'' $$

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

    • 方案1

      $$ P'= {p_1(<t_1, t_2>, t_1, t_1+t_2), p_2(<t_{n-1}, t_n>, t_2, t_2+t_n)} $$

      $$ Ts' = (t_1+t_2)+(t_2+t_n) = t_1 + 2t_2 + t_n $$

    • 方案2

      $$ P'' = {s_1(<t_1, t_n>, t_1, t_1+t_n), s_2(<t_1, t_{n-1}>, t_1, t_1+t_{n-1})} $$

      $$ s'' = (t_1+t_n)+(t_1+t_{n-1})= 2t_1 + t_{n-1} + t_n $$

    • 选择用时最少方案

      $$ \Delta T = Ts'' - Ts'= (2t_1 + t_{n-1} + t_n) -( t_1 + 2t_2 + t_n) = t_1 + t_{n-1} - 2t_2 $$

      $$ P, Ts = \Delta T > 0 ? (P', Ts') : (P'', T_s'') $$

    那么,用时最少的时间:$$TS += Ts, N -= 2(当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 if A.length == 3:
        for i = 1 to A.length:
            Ts += A[i]
    else
        Ts += (A.length == 2) ? A[2] : A[1]

//迭代
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
    if i == 3:
        for i = 1 to 3:
            Ts += A[i]
    else
        Ts += (i == 2) ? A[2] : A[1]

跳跃游戏

题目转自LeetCode:https://leetcode-cn.com/probl...

给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。

分析
解决问题的核心是选择当前可以跳跃的最大长度内的最大元素所在的位置,即是从当前位置要跳跃到下一个位置。

解决方案

//递归
steps = 0
Jump(A, curPos = 0):
    maxValue = 0
    nextPos = 0
    for i = curPos + 1 to curPos + A[curPos]:
        curValue = A[i]    //循环遍历可以跳跃长度内的元素值
        if curValue > maxValue:
            maxValue = curValue
            nextPos = i //最大值的位置即是要跳跃的下一个位置
    steps++
    if nextPos >= A.lenght:  //递归结束条件
        return
    Jump(A, nextPos)

评论

暂无评论