502. IPO

https://leetcode-cn.com/problems/ipo/

假设力扣（LeetCode）即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后得到最大总资本的方式。

给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。

示例 1:

输入: 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 位有符号整数范围内。

通过次数2,982 | 提交次数7,607

First Try

2020-06-27

印象中这应该是第一个双百版本,第一次使用heap堆这种数据结构解决问题，但依然是看了题解之后才做出来的题目。

一开始没有正确理解题意，以为是在有限的资金里安排费用进行项目采购之类，想到的只有暴力递归法，但是结果只能是超时。后来才发现是每次选择一个项目之后，该项目都能够马上得到新的净利润，在不同项目之间投资也没有时间要求，这就变得容易多了，每次选可选项目中利润最高的即可。

但是没有使用heap数据结构的话，还是轻轻松松就挂掉了，毕竟每次都需要根据新赚到的资金进行选择，结果就是N次排序。

改成heap之后，每次排序其实只耗费O(lgN)时间，第一次感受到heap的好处。对于不符合要求的元素也按堆进行存储，每次新增利润后，从废弃堆里面拿符合要求的扔到选择堆中，又加快了速度。

另外，python的heap只有最小堆，如果需要使用最大堆的话，只能把元素进行反转，处理的时候注意点就行。 k = -k这样子操作，极小堆就是极大堆，这也是标准操作。

https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python

The easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.

import heapq

class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capital):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """ 
        # oops, 知道了思路和捷径还是超出时间限制了
        # 重点在于每次开销后都能挣回来，而不是拿有限的钱进行开支
        # 每次收益高了还要重新排序，只能上堆了，不然tmd又超时了
        if W >= max(Capital):
            return W + sum(heapq.nlargest(k, Profits))  # 之前忘记额外加上W了
        # print("WTF")
        heap = []
        excluded = []
        # 一开始就把所有heap构建好，但刚开始从大到小每次删除还是很耗费时间，记得删除一个耗时O(N)
        for i in range(len(Profits)):
            heapq.heappush(heap, (-Profits[i], Capital[i], i))
        while k > 0 and len(heap):  # 
            p, c, i = heapq.heappop(heap)  # minimum heap, p should be negative
            if c > W:
                heapq.heappush(excluded, (c, p, i))
                # excluded.append((p, c, i))
                continue
            W += (-p)
            k -= 1
            while len(excluded):
                c, p, i = heapq.heappop(excluded)
                if c <= W:
                    heapq.heappush(heap, (p, c, i))
                else:
                    heapq.heappush(excluded, (c, p, i))
                    break
            # tmd又写出了一个bug,excluded只增不减，差点陷入无限循环，最后把excluede也改成堆了
            # for (p, c, i) in excluded:
                # if c <= W:
                #     heapq.heappush(heap, (p, c, i))
        return W

            

执行用时：36 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：16.8 MB, 在所有 Python 提交中击败了100.00%的用户

Time Exceeded Version

总共写出了三个超时版本。

了解题意之后的版本

但是没有使用heap数据结构，依然超时。

class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capital):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """ 
        # oops, 知道了思路和捷径还是超出时间限制了
        # 重点在于每次开销后都能挣回来，而不是拿有限的钱进行开支
        pxc= [(Profits[i], Capital[i], i) for i in range(len(Profits))]
        
          每次来一波排序实在太耗时了
        def sort_pxc(pxc, max_c, invested):
            allowed = [pxc[i] for i in range(len(pxc)) if pxc[i][2] not in invested and pxc[i][1] <= max_c]
            # return max(allowed) # 可能allowed为空，导致max([])报错
            if not allowed:
                return (0, 0, -1) # marked poinot
            return max(allowed)

        invested = set()
        while k > 0 and len(pxc):
            (p, c, idx) = sort_pxc(pxc, W, invested)
            if idx == -1:
                return W
            W += p
            invested.add(idx)
            k -= 1
        return W

递归+缓存的版本

没有理解题意，而且这个题用缓存也太别扭了。

# 超时挂掉了，思路理解错误
class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capital):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """

        # 使用回溯法+暴力遍历？ 哪里可以剪枝呢，应该会超时。。。
        # 果然超时了。缓存有两个需要注意的地方，k和invested，只要一致就行
        # 使用缓存后还是超时了，这就很难搞了啊，这种多重策略选择的
        # 而且求的还是最大值，找不到方法快速退出？

        if not Profits or not Capital:
            return 0
        list_to_str = lambda x: ''.join([str(i) for i in x])
        cache = dict()
        def back_track(k, W, Profits, Capital, invested):
            # print(k, W, Profits, Capital, invested)
            if k == 0 or W < min(Capital):
                return W
            if (k, list_to_str(invested)) in cache:
                return cache[(k, invested)]
            col = []
            for i in range(len(Capital)): 
                if i not in invested and Capital[i] <= W:
                    invested.append(i)
                    s = back_track(k-1, W + Profits[i], Profits, Capital, invested)
                    # print(i, s)
                    col.append(s)
                    invested.pop()
            # 当所有可以投资的都被投资了，后果是col保持空集结果，需要返回W
            rv = max(col) if col else W  # curcial point
            cache[(k, list_to_str(invested))] = rv
            return rv

        maxw = back_track(k, W, Profits, Capital, [])
        return maxw     

递归穷举版本

其实能写出这个版本已经很不错了，但是没有理解到题意的精髓，也没用上贪心算法，结局只能是超时。

class Solution(object):
    def findMaximizedCapital(self, k, W, Profits, Capital):
        """
        :type k: int
        :type W: int
        :type Profits: List[int]
        :type Capital: List[int]
        :rtype: int
        """

        # 使用回溯法+暴力遍历？ 哪里可以剪枝呢，应该会超时。。。
        # 果然超时了

        if not Profits or not Capital:
            return 0

        def back_track(k, W, Profits, Capital, invested):
            # print(k, W, Profits, Capital, invested)
            if k == 0 or W < min(Capital):
                return W
            col = []
            for i in range(len(Capital)): 
                if i not in invested and Capital[i] <= W:
                    invested.add(i)
                    s = back_track(k-1, W + Profits[i], Profits, Capital, invested)
                    # print(i, s)
                    col.append(s)
                    invested.remove(i)
            # 当所有可以投资的都被投资了，后果是col保持空集结果，需要返回W
            return max(col) if col else W  # curcial point
        
        maxw = back_track(k, W, Profits, Capital, set())
        return maxw            

502. IPO​

First Try​

Time Exceeded Version​

502. IPO

First Try

Time Exceeded Version