【算法】（Python）贪心算法

2024-11-05 08:47:25

贪心算法：

又称贪婪算法，greedy algorithm。
贪心地追求局部最优解，即每一步当前状态下最优选择。
试图通过各局部最优解达到最终全局最优解。但不从整体最优上考虑，不一定全局最优解。
步骤：从初始状态拆分成一步一步的，每一步确保当前状态最优解，再下一步。
关键：具体的贪心策略（选择能产生问题最优解的最优度量标准）。
使用条件：贪心选择（一个问题最优解可通过一系列局部最优解达到，每一步可依赖以前的选择，不可回溯），最优子结构（一个问题最优解包含其子问题的最优解）。

案例：

1、（难度：简单）【力扣】1710. 卡车上的最大单元数

解题思路：每一步优先挑选当前可装载的最大单元数量的箱子。

将列表按单元数量（元素中下标为1的值）降序排列。
遍历列表中所有元素，
若当前元素的箱子最大数量已经达到指定总数量，则单元总数=指定总数量*单元数量，并结束，返回单元总数。
若当前箱子最大数量在指定总数量之内，则当前箱子最大数量*单元数量，累加到单元总数中，剩余指定总数量=指定总数量-当前箱子最大数量；
再判断列表中下一个元素，
直到遍历完列表中所有元素，或者达到指定总数量，返回单元总数。

知识点：列表.sort(key=排序条件, reverse=True)：列表按照排序条件降序排列。

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        # 将列表按单元数量（即各元素下标为1的值）降序排列
        boxTypes.sort(key=lambda x: x[1], reverse=True)
        
        total = 0         # 记录可装载的单元总数
        # 遍历列表，指定最大数量依次减去最大箱子数量计算剩余数量，并统计单元总数
        # i为箱子数量，j为每个箱子的单元数量
        for i, j in boxTypes:
            if i >= truckSize:
                total += truckSize * j
                break
            total += i * j
            truckSize -= i
        return total

2、（难度：中等）【力扣】714. 买卖股票的最佳时机含手续费

解题思路：买卖为一次交易、计算一次手续费，则买入时计算手续费。买入价尽可能当前最低价，卖出价尽可能当前最高价。

初始买入价为列表第一日价格（含手续费），
依次遍历列表中每日价格，
若当前价（含手续费）<买入价，即当前价格比前一天低，则当前价（含手续费）为新的买入价。若当前价（不含手续费）>买入价，则假装卖出，计算利润（若前一日也假装卖出则利润加上当前价与前一日的差价），并假装当天免手续费买入，即当天价（不含手续费）为买入价，
下一日价格，当前价再与买入价比较。
遍历完列表所有元素，返回总利润。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        profit = 0                # 记录总收益
        buy = prices[0] + fee     # 初始买入
        # 遍历每个价格
        for i in prices:
            # 若当前价+手续费<买入价，则当前价买入
            if i + fee < buy:
                buy = i + fee
            # 当前价格>买入价，（假装卖出）计算利润（当前价与买入价的差），
            # 并假装以当前价免手续费买入（若明天价比当前价高，明天收益就是明天价与当前价之间的差）
            elif i > buy:
                profit += (i - buy)
                buy = i
        return profit

注：本题其他解题方法：动态规划。本文忽略。

3、（难度：困难）【力扣】871. 最低加油次数

解题思路：一个优先队列记录每个加油站的加油量（降序，最大油量在前）。计算每到一个地方的剩余油量，若不足则优先使用最大油量加油。

遍历每个地方和目的地（n+1），
计算从上一个位置到达当前地方后的剩余油量，
若剩余油量不足，则依次从优先队列取出最大油量加油，每加一次统计一次，直到加满或优先队列为空（即没有油可加），
若加完油后剩余油量仍不足，则无法到达目的地，返回-1，
每到达一个加油站，将加油量添加到优先队列，并将当前地方设为上一位置，用于下一个地方计算判断油量。

知识点：二维数组[子数组下标][子数组中元素下标]：获取二维数组中元素。二维数组：数组中的元素类型仍为数组。

python中heapq库用于操作堆（最小堆，最大堆），应用于优先队列和堆排序。此处为优先队列。

heapq.heappush(队列, 元素)：往优先队列添加元素，自动生成最小堆（父节点小于所有子节点，左右子节点无大小要求）。元素前加负号“-”，则各元素负数后的最小堆，类似最大堆，取出时前面也加负号“-”即为最大值。

heapq.heappop(队列)：从优先队列中取出最小值。

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:       
        import heapq
        res = 0               # 统计加油次数
        fuel_list = []        # 油量优先队列（最大的在前），记录每个加油站的加油量
        fuel = startFuel      # 记录目前油量
        pre = 0               # 记录上一个位置
        # 遍历每个加油站和目的地
        n = len(stations)
        for i in range(n + 1):
            # 记录当前位置,若加油站则为元素中下标为0的值，若目的地则为target
            if i < n: cur = stations[i][0]
            else: cur = target
            # 计算达到当前位置，剩余油量
            fuel -= cur - pre
            # 若剩余油量<0,且油量优先队列中有元素，依次按最大油量加油，直到加满或油量优先队列为空
            while fuel < 0 and fuel_list:
                # 油量优先队列为了从大到小排列，元素是负数
                fuel += (-heapq.heappop(fuel_list))           # 从优先队列取出最大值
                res += 1
            # 若加油后，剩余油量仍<0，说明即使加满油也到不了目的地
            if fuel < 0: return -1
            # 每到一个加油站，将油量添加到油量优先队列中
            if i < n:
                # 油量优先队列为了从大到小排列，元素是负数
                heapq.heappush(fuel_list, -stations[i][1])    # 添加到优先队列（最大堆）
                pre = cur
        return res

注：本题其他解题方法：动态规划。本文忽略。

码农公寓

相关文章