输入： 参数1，正数数组costs 参数2，正数数组profits 参数3， 正数k 参数4，正数m costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花 费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多做k个项目 m表示你初始的资金 说明：你每做完一个项目，马上获得的收益，可以支持你去做下 一个 项目。 输出： 你最后获得的最大钱数
思想 :以项目成本做一个小根堆,将小根堆里小于等于本金的项目加入以项目利润构成的大根堆,在k次以内,每次取最大利润的项目做,若达到k次或者自己成本内没有可以做的项目结束.
代码
代码语言：javascript复制package com.algorithm.practice.heap;
import java.util.Comparator;
import java.util.PriorityQueue;
public class MakeMoreMoney {
public class Node{
int cost;
int getM;
public Node(int c,int g){
this.cost=c;
this.getM=g;
}
}
public class minHeapCompartor implements Comparator<Node>{ //以成本打造小根堆
@Override
public int compare(Node n1,Node n2) {
return n1.cost-n2.cost;
}
}
public class MaxHeapCompartor implements Comparator<Node>{ //以利润打造大根堆
@Override
public int compare(Node n1,Node n2) {
return n2.getM-n1.getM;
}
}
public int makeMoreMoneyint (int k, int W, int[] Profits, int[] Capital){
//k 可以做项目的次数, W 资本, Profits 利润, Capital 成本
Node[] progectS=new Node[Profits.length];
for(int i=0;i<progectS.length;i ){//添加成本和利润构成项目集
progectS[i]=new Node(Capital[i],Profits[i]);
}
//建造成本小根堆
PriorityQueue<Node> capitalQueue=new PriorityQueue<>(new minHeapCompartor());//指定小根堆比较器
for(int i=0;i<progectS.length;i ){
capitalQueue.add(progectS[i]);
}
PriorityQueue<Node> profitsQueue=new PriorityQueue<>(new MaxHeapCompartor());//指定大根堆比较器
for(int i=0;i<k;i ){
while (!capitalQueue.isEmpty()&&capitalQueue.peek().cost<=W){
profitsQueue.add(capitalQueue.poll());
}
if (profitsQueue.isEmpty()){
return W;
}
W =profitsQueue.poll().getM;
}
return W;
}
}
