502 IPO（贪心、大根堆维护元素最大值）

港控/mmm° 2022-08-29 15:49 121阅读 0赞

**1. 问题描述：**

假设力扣（LeetCode）即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后得到最大总资本的方式。  
给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。  
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。

**示例：**  
输入：k=2, W=0, Profits=\[1,2,3\], Capital=\[0,1,1\].  
输出：4  
解释：  
由于你的初始资本为 0，你仅可以从 0 号项目开始。  
在完成后，你将获得 1 的利润，你的总资本将变为 1。  
此时你可以选择开始 1 号或 2 号项目。  
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。  
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。  
提示：  
假设所有输入数字都是非负整数。  
表示利润和资本的数组的长度不超过 50000。  
答案保证在 32 位有符号整数范围内。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ipo

**2. 思路分析：**

分析题目的数据范围50000那么可能使用二分查找或者是**贪心**的思路解决（不可能是递归），分析题目可以知道贪心的思路可能会更正确一点。我们可以先考虑一下贪心，对于贪心的题目有一个基本的套路就是按照某个策略对数组进行排序，然后从前往后遍历数组，每一次只会选择一个集合，因为选择这个集合的时候肯定值最优的那么就不用考虑其他集合了。首先题目有一个限制就是只有当当前的成本小于手中的资本的时候才可以选择当前的项目。所以我们可以想到的策略是在能够选择项目的前提下选择出利润最大的那个项目那么肯定是最优的，这样在启动完当前可以选择的项目之后获得的利润是最大的然后又可以启动下一个可以选择的项目了，其他的选择方式肯定不是最优的。所以我们可以按照启动资金和利润作为一个整体从小到大排序，因为使用的是python语言所以可以直接使用zip函数将Capital和Profits映射为一一对应的组合，使用list函数zip对象转换为列表排序即可，并且我们需要使用一个数据结构来维护当前集合中元素的最大值得到当前可选项目的最大利润，这里可以使用一个大根堆来维护当前可选项目的最大值，可以使用heapq模块中的方法来维护堆，由于python没有大根堆但是可以在元素前面添加负号表示大根堆，每一次将可以选择项目的时候将利润的相反数添加到堆中即可，堆顶元素的相反数那么就是当前项目可以获得的最大利润的相反数，我们可以将最大利润累加到w中即可然后继续选择下一个项目，如果没有项目可选那么直接break。一般我们**首先考虑做出来**，其次考虑使用什么样的**数据结构进行优化**。

**3. 代码如下：**

from typing import List
    import heapq
    
    
    class Solution:
        def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
            # zip函数将两个列表的元素一一对应
            q = list(zip(capital, profits))
            q.sort()
            # 使用列表表示堆, 后面就可以使用heapq模块的方法来维护堆
            heap = list()
            i, n = 0, len(profits)
            while k > 0:
                # 将所有可以选择的项目加入到堆中
                while i < n and q[i][0] <= w:
                    # 添加负号相当于是大根堆
                    heapq.heappush(heap, -q[i][1])
                    i += 1
                # 没有项目可以加入进来break
                if len(heap) == 0: break
                # 堆中维护的是可选项目利润的相反数, 堆顶就是可选项目的最大利润的相反数
                t = heapq.heappop(heap)
                # 能够启动该项目所以需要加入该项目的资金
                w += -t
                k -= 1
            return w