算法-贪心+优先级队列-IPO

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/ipo/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

2 回溯法

2.1 思路

2.2 代码

class Solution {int result = 0;public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {Set<Integer> set = new HashSet<>();for (int i = 0; i < profits.length; i++) {set.add(i);}backtrack(k, w, profits, capital, set);return result;}// r 表示还能选的项目数// t 表示当前资本总数// Set 可选的项目序号private void backtrack(int r, int t, int[] profits, int[] capital, Set<Integer> set) {// 结束条件if (r == 0) {result = Math.max(result, t);return;}List<Integer> list = new ArrayList<>(set);int select = 0;// 路径选择for (Integer i : list) {// 选择if (t >= capital[i]) {select++;t += profits[i];set.remove(i);r--;// 递归回溯backtrack(r, t, profits, capital, set);// 撤销选择r++;t -= profits[i];set.add(i);}}if (select == 0) {// 一个都没选，也是结束条件result = Math.max(result, t);}}
}

2.3 时间复杂度

直接超时了，选择路径太多了

3 贪心法+优先级队列

2.1 思路

整体思路就是，每次都贪心选择可选项目中利润最大的项目，最后累加得到最大利润。

1. 把项目按最低成本要求升序排序所有项目
2. 每次将符合成本要求的项目放入以利润排序的大顶堆
3. 贪心的取大顶堆堆顶的项目，累加利润到成本后，继续下次判断和选择
4. 如果可选项目数为0或者大顶堆为空了，代表选择完毕

2.2 代码

class Solution {class Node {public int index;public int profit;public int capital;public Node(int index, int profit, int capital) {this.index = index;this.profit = profit;this.capital = capital;}}int result = 0;public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {// 可选的项目综合信息List<Node> projectList = new ArrayList<>();for (int i = 0; i < profits.length; i++) {projectList.add(new Node(i, profits[i], capital[i]));}// 把项目按最低成本要求升序排序Collections.sort(projectList, (o1, o2) -> o1.capital - o2.capital);greed(k, w, projectList, new PriorityQueue<>((o1, o2) -> o2.profit - o1.profit), 0);return result;}// r 表示还能选的项目数// t 表示当前资本总数// projectList 按最低成本从小到大排序的列表// priorityQueue 按项目利润排序的大顶堆// i 当前可选择序号private void greed(int r, int t, List<Node> projectList, PriorityQueue<Node> priorityQueue, int i) {// 结束条件if (r == 0) {result = Math.max(result, t);return;}// 将符合成本要求的项目放入利润大顶堆while (i < projectList.size()) {if (t >= projectList.get(i).capital) {priorityQueue.add(projectList.get(i));i++;} else {break;}}if (priorityQueue.size() == 0) {// 一个都不符合要求result = Math.max(result, t);return;}// 贪心的选择能选的项目里利润最高的Node maxNode = priorityQueue.poll();t += maxNode.profit;// 继续选下一个项目greed(--r, t, projectList, priorityQueue, i);}
}

2.3 时间复杂度

2.4 空间复杂度

O(n)

• 构建大顶堆、数组