本文共 1282 字,大约阅读时间需要 4 分钟。
假设 LeetCode 即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司,LeetCode希望在 IPO 之前开展一些项目以增加其资本。
由于资源有限,它只能在 IPO 之前完成最多 k 个不同的项目。帮助 LeetCode 设计完成最多 k 个不同项目后得到最大总资本的方式。
给定若干个项目。对于每个项目 i ,它都有一个纯利润 P i,并且需要最小的资本 C i 来启动相应的项目。最初,你有 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。
def ipo(K, W, Profit, Capital): while K > 0: K -= 1 Profits = [] S = [] if W == 0: for index, value in enumerate(Capital): if value == 0: Profits.append(Profit[index]) W = max(Profits) if W > 0: for i in range(len(Capital)): s = Profit[i] - Capital[i] S.append(s) max_index = S.index(max(S)) W += Profit[max_index] return W
首先,通过不断迭代K(项目),然后判断W(资本),判断其是否为0, 如果为0的话,则首先选择启动资金Capital也为0的项目,然后判断Captial=0时,选择对应Profit位置中最大值。如果W不为零,则遍历所有Profit和Capital的差值, 去对应最大值, 最后求得最大值所有,再累加到W上。直至到最后一个K为止,结束循坏,返回结果。
多思考,多练习!
转载地址:http://vpwpi.baihongyu.com/