题目描述
给定两个整数W和K，W代表你拥有的初始资金，K代表你最多可以做K个项目。再给定两个长度为N的正数数组costs[]和profits[]，代表一共有N个项目，costs[i]和profits[i]分别表示第i号项目的启动资金与做完后的利润(注意是利润，如果一个项目的启动资金为10，利润为4，代表该项目最终的收入为14)。你不能并行只能串行地做项目，并且手里拥有的资金大于或等于某个项目的启动资金时，你才能做这个项目。该如何选择做项目，能让你最终的收益最大？返回最后能获得的最大资金
时间复杂度为O(klogn)，空间复杂度为O(n)
public static int maxProfit(int w, int k, int[] cost, int[] profits) { int n = cost.length; if(w < 1 || k < 0) return w; Queue<int[]> queue1 = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]); // 小根堆 花费升序 Queue<int[]> queue2 = new PriorityQueue<>((o1,o2)->o2[1]-o1[1]); // 大根堆 利润降序 for(int i = 0; i < n; i++) { queue1.add(new int[]{cost[i],profits[i]}); //初始都加入花费小根堆 } while(k != 0) { // k != 0 循环 while (!queue1.isEmpty() && w >= queue1.peek()[0]) { queue2.add(queue1.poll()); } // 每次先解锁所有可做项目，放入利润大根堆，选最大的做 if(queue2.isEmpty()) break; w += queue2.poll()[1]; // 做完跟新当前最大利润 k--; } return w; }
原文：https://www.cnblogs.com/yonezu/p/13263271.html