假设 力扣（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 位有符号整数范围内。
题解
本题是一个标准的贪心问题, 每一轮投资可以分为两步, 先将所有项目按成本 C 排序放入一个小根堆中, 再将所有成本小于现有资本的项目弹出, 按纯利润 P 排序放入另一个大根堆中, 弹出利润最高的元素, 将利润 P 与原资本相加得到新的资本, 循环以上步骤, 直至做完 k 个项目.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| public class MaximizedCapital {
static class Node {
public int p;
public int c;
public Node(int p, int c) {
this.p = p;
this.c = c;
}
}
public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<Node> minCost = new PriorityQueue<>((a, b) -> {
return a.c - b.c;
});
PriorityQueue<Node> maxProfit = new PriorityQueue<>((a, b) -> {
return b.p - a.p;
});
for (int i = 0; i < Profits.length; i++) {
minCost.add(new Node(Profits[i], Capital[i]));
}
for (int i = 0; i < k; i++) {
while (!minCost.isEmpty() && minCost.peek().c <= W){
maxProfit.add(minCost.poll());
}
if (maxProfit.isEmpty()){
return W;
}
W += maxProfit.poll().p;
}
return W;
}
}
|
Python
计算利润时, 成本不影响结果, 故可只取利润存入列表中.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class MaximizedCapital:
class MaximizedCapital:
def findMaximizedCapital(self, k, W, Profits, Capital):
captal = sorted(list(zip(Capital, Profits)), key=lambda x: -x[0])
profit = []
for i in range(k):
while captal and captal[-1][0] <= W:
profit.append(captal.pop()[1])
tmp_max = max(profit) if profit else 0
W += tmp_max
if profit:
profit.remove(tmp_max)
return W
|