S'S ALGORITHM

贪心算法相关问题

---

概念解析

贪心算法（又称贪婪算法）是一种在对问题求解时，总是做出在当前看来是最好的选择，从而希望导致结果是最好或最优的算法。它是一种启发式算法，不保证一定能找到全局最优解，但通常情况下能找到较好的解。也就是说它是一种局部最优求解法。

贪心算法可以用于解决各种类型的优化问题，例如：

• 覆盖问题: 在给定一组集合的情况下，选择尽可能少的集合来覆盖所有元素。
• 分配问题: 将一组任务分配给一组机器，使得每台机器的负载最小化。
• 调度问题: 为一组任务安排一个顺序，使得完成所有任务所需的时间最短。
• 路径规划问题: 在给定一张图的情况下，找到从一个点到另一个点的最短路径。

这种算法简单易懂，易于实现。即使对于大规模问题，也能够在较短时间内找到解。然而它不保证一定能找到全局最优解。在某些情况下，可能找到非常差的解。

贪心算法是一种简单有效的启发式算法，可以用于解决各种类型的优化问题。尽管它不保证一定能找到全局最优解，但通常情况下能找到较好的解。在实际应用中，贪心算法经常与其他算法结合使用，以提高求解效率。

问题1:Jump Game I

给你一个非负整数数组 nums，你最初站在数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。以此判断你是否能够到达最后一个位置。以下是一个例子。

输入: nums = [2, 3, 1, 1, 4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1，然后再跳 3 步到达最后一个位置。

这个问题可以用贪心算法来解决。贪心算法的基本思想是：在解决问题时，总是做出在当前看来是最好的选择，希望最终能够得到一个全局最优解。如果使用暴力解法，是用回溯不断探索每次可以跳到的位置，如果无法触及最后，就回溯重新走，和遍历棋盘的意义一样，但是回溯的时间复杂度是指数级别的。

解题步骤：

• 从数组的最后一个位置开始往前遍历，设定目标位置 target 为数组的最后一个位置（即初始时为 n - 1）。
• 对于当前位置 i，判断是否能够跳到目标位置 target。如果能够跳到目标位置，则将目标位置更新为当前位置 i。
• 最后，判断目标位置是否为数组的第一个位置，如果是，则说明能够跳到最后一个位置，否则不能。

代码尝试：

def jump_game(nums):
    target = len(nums) - 1
    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= target:
            target = i
    return target == 0

学习笔记：该算法的时间复杂度为 O(n)，其中 n 是数组的长度。该算法的空间复杂度为 O(1)，因为它只需要使用一个变量来记录当前能够到达的最后位置。

问题2:Boats to Save People

有一艘大船，你可以假设它就是泰坦尼克，需要对船上的人进行救援，救生船的数量无限制。如何用最少的船的数量，救所有的人。

已知 input 数据：people，是乘客的重量列表。limit是每艘船的重量上限。同时，每艘船空间上最多可以坐2个人。单个人不会超过船的载重限制。

题解思路：

• 将people列表从小到大排列。
• 初始化两个指针 left 和 right 分别指向列表的开始和结尾。
• 从两头开始遍历列表，检查最轻的人和最重的人的组合是否不超过船载重限制。
  • 若是则向中间移动两个指针一步，若否则只载重的人，将右指针向左移动一步。
  • 增加一艘船的数量。
• 当所有指针相遇，结束遍历，返回船的数量。

代码尝试：

def rescue_boats(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    count = 0

    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1
        count += 1

    return count

下面是给出的参考答案，简化了几行代码：

def rescue_boats(people, limit):
    people.sort()
    left = 0
    right = len(people) - 1
    boats = 0  

    while left <= right:  
        if people[left] + people[right] <= limit:
            left += 1  
        right -= 1
        boats += 1 
    return boats

学习笔记：这道题只要想好并跟着解题思路写就很简单，贪心算法难的不是内部逻辑，而是人的解题思维，这么看来确实是一种符合直觉的解题方法。这道题的时间和空间复杂度集中在对列表的排序上，时间复杂度O(nlogn)，空间复杂度O(n)。

问题3:Minimum Number of Refueling Stops

（力扣871题，是hard难度的。）

假设你正在驾驶一辆汽车，从美国的西部穿越到东部，你知道这辆汽车的初始位置、终点位置以及汽车每次加满油能行驶的距离。此外，你还知道一系列加油站的位置和它们提供的油量。你需要确定在不进行过多次加油的情况下，是否能够到达终点，并且如果可以的话，最少需要加几次油。

简而言之，题目要求你计算出最少的加油次数，以确保汽车能够从起点行驶到终点。

假设 stations 的列表：[[2, 5], [3, 1], [6, 4], [12, 6]]。第一个元素是加油站和起点之间的距离，第二个元素是在该加油站可以加多少油。

如果给定一个目标距离：target = 15，以及一个初始油量 start_fuel 为 3。

那么计算过程如下：

• 首先用油量 3，可以行驶到最远的距离第一个加油站，这时候的油量为 3 - 2 = 1，在站内加油后，为 1 + 5 = 6。
• 使用油量 6，最远可以行驶到第三个加油站，它距离当前距离为 6 - 2 = 4，行驶到第三个加油站后，还有 6 - 4 = 2 单位油，加油后为 2 + 4 = 6 单位油。
• 最后使用 6 单位油可以行驶到距离当前，也就是第三个油站外 12 - 6 = 6 距离到第四个加油站，到达后油耗尽，但是可以加 6 单位油。
• 还有 15 - 12 = 3 单位距离可以到达目的地，但是我们还有 6 单位油，所以总结，加三次油就可以到达目的地，油站为1，3，4号。

解题思路：

• 如果初始油量本就大于或者等于 target，那么不需要加油就可以到达，直接 return 0。
• 初始化一个 cur_fuel 表示当前油量，一个 max_fuel 用于更新最大可加油量，一个 stops 用于存放油站数量。
• 遍历 stations 列表，终止条件是可以走的最大距离小于 target，并且油量没有耗尽。
• 不断更新当前油量为 cur_fuel + max_fuel，如果可更新的最大油量为 0 ，也就是到不了下一个加油站，那么返回 -1。
• 最终返回 stops。

我进行了一个代码尝试：我的解法完全是贪心算法的尝试，每次都行驶到可以加油最大量的加油站，在这个示例中我得到了解。但是当示例变成：

stations = [[2, 5], [3, 1], [6, 3], [12, 6]]

的时候，注意第三个车站的加油数量变成了3，这时候我的代码得到的就是 -1，也就是没有解答，但是其实是可以在第二个油站加到一单位的油的。

def min_refuel_stops(target, start_fuel, stations):

    if start_fuel >= target:
        return 0

    cur_fuel = start_fuel
    stops = 0
    idx = 0
    while cur_fuel < target:
        max_fuel = 0
        while idx < len(stations) and stations[idx][0] <= cur_fuel:
            max_fuel = max(max_fuel, stations[idx][1])
            idx += 1

        print(cur_fuel, max_fuel)
        if max_fuel == 0:
            return -1

        cur_fuel += max_fuel
        stops += 1

    return stops


stations = [[2, 5], [3, 1], [6, 4], [12, 6]]
target = 15
start_fuel = 3
res = min_refuel_stops(target, start_fuel, stations)
print(res)

这是一个常见的问题，贪心算法在某些情况下可能会错过最优解。在这个问题中，贪心算法可能会选择在每个加油站加入尽可能多的油，而不考虑后续的加油站分布和可能的最优路径。这可能导致在某些情况下，即使有足够的加油站，但由于贪心选择的不当，车辆最终无法到达终点。

为了解决这个问题，可以考虑使用动态规划算法。动态规划算法可以在每个加油站决策时考虑当前状态和后续可能的状态，并选择最优的路径来到达终点。

以下是一个使用动态规划算法解决这个问题的示例代码：

def min_refuel_stops(target, start_fuel, stations):
    # dp[i]表示在加满i次油的情况下，能到达的最远距离
    dp = [start_fuel] + [0] * len(stations)
    for i in range(len(stations)):
        for j in range(i, -1, -1):
            if dp[j] >= stations[i][0]:
                dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1])

    for i in range(len(dp)):
        if dp[i] >= target:
            return i

    return -1


stations = [[2, 5], [3, 1], [6, 3], [12, 6]]
target = 15
start_fuel = 3
res = min_refuel_stops(target, start_fuel, stations)
print(res)

这个动态规划算法会考虑所有可能的加油次数，并选择最优的方案来到达终点。这样可以避免贪心算法可能出现的问题，确保找到最优解。

我所用的题库给出的题解如下：（已经将注释加在了代码里

import heapq

def min_refuel_stops(target, start_fuel, stations):
    if start_fuel >= target:  # 如果初始油量已经足够到达目标距离，则返回 0
        return 0

    max_heap = []  # 初始化一个最大堆，用于存储加油站的油量信息
    i, n = 0, len(stations)  # 初始化当前考虑的加油站索引 i 和加油站的总数 n
    stops = 0  # 初始化加油次数为 0
    max_distance = start_fuel  # 初始化最大行驶距离为初始油量

    while max_distance < target:  # 循环直到最大行驶距离超过目标距离
        if i < n and stations[i][0] <= max_distance:  # 如果当前考虑的加油站的位置小于等于最大行驶距离
            heapq.heappush(max_heap, -stations[i][1])  # 将该加油站的油量（负值，因为要使用最大堆）加入堆中
            i += 1  # 将索引 i 向后移动一位，准备考虑下一个加油站
        elif not max_heap:  # 如果堆为空，表示无法到达下一个加油站
            return -1  # 返回 -1，表示无解
        else:  # 否则，说明当前的油已经用完，需要加油
            max_distance += -heapq.heappop(max_heap)  # 从堆中取出油量最多的加油站的油量，并加到当前油箱中
            stops += 1  # 增加加油次数

    return stops  # 返回加油次数，即达到目标距离所需的最少加油次数

这个方法重要的地方在于综合利用贪心算法和最大堆，能够在保证尽可能少的加油次数的前提下，确保汽车能够到达目标距离。通过动态地管理油量信息，并始终保持最大行驶距离，算法能够在每一步选择最优的加油策略，从而达到问题的最优解。

学习笔记：单纯地使用贪心可能会错过最优解，题解使用最大堆控制了这个问题，或者直接用动态规划解题。

分析一下动态规划方法和上面的贪心加最大堆方法的时间和空间复杂度。

贪心加最大堆方法：

• 时间复杂度：
  • 首先，将加油站的油量信息加入最大堆中的时间复杂度为 O(nlogn)，其中 n 是加油站的数量。
  • 在每次迭代中，从堆中取出最大的油量，以及加油站的位置信息，然后根据当前汽车的位置和油量，决定是否需要加油。这一步的时间复杂度为 O(logn)，因为堆的插入和删除操作的时间复杂度都是对数级别的。
  • 因此，总体的时间复杂度为 O(nlogn)。
• 空间复杂度：
  • 最大堆所需要的额外空间取决于加油站的数量，因此空间复杂度为 O(n)。

动态规划方法：

• 时间复杂度：
  • 动态规划方法的时间复杂度取决于两层循环的次数，其中外层循环是加油站的数量 n，内层循环是加油次数 i。因此，总体的时间复杂度为 O(n^2)。
  • 在每次内层循环中，需要比较当前加油次数下到达每个加油站的最大距离，这一步的时间复杂度为 O(n)，因此总体的时间复杂度为 O(n^3)。
• 空间复杂度：
  • 动态规划方法需要一个长度为 n+1 的数组来存储每次加油后能到达的最远距离，因此空间复杂度为 O(n)。

从时间和空间复杂度的角度来看，贪心加最大堆方法在时间上比动态规划方法更优，但在空间上两者相当。然而，贪心加最大堆方法可能会因为贪心选择的不当而错过最优解，而动态规划方法能够保证找到最优解。因此，在实际应用中，需要根据具体问题的特点来选择合适的算法。