贪心算法之利润最大问题

力扣第502题：

题目解释：

每个项目有不同的花费，也有不同的利润，capital数组就是项目的花费，profit数组就是项目的利润，索引i就是对应的项目，给定启动资金W，最多完成K个项目，怎么安排利润最大，求最大利润

解题步骤：

1.定义项目类（Project），两个属性：项目花费cost和项目利润profit

2.定义一个小根堆、一个大根堆，小根堆以项目花费最少的排序，大根堆暂时位空

3.从小根堆弹出项目，如果项目花费小于启动资金W，那么就把满足条件的项目全部加入大根堆，大根堆以利润最大排序（注意提前自定义比较器，因为Project类是自定义的，没有比较器的话系统不知道怎样比大小）

4.从大根堆依次拿出项目，将利润累加到W，直到大根堆为空或者小根堆的项目都大于启动资金W结束

整体代码：

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 题目解释：
 * 初始资金W，最多最K个项目，每个项目可以挣到不等的钱，求怎么组合挣到的钱最多？
 */
public class Code_502 {

    public static class Project {
        public int cost;
        public int profit;

        public Project(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

    //花费较小的排在前面的比较器
    public static class CostComparator implements Comparator<Project> {
        @Override
        public int compare(Project o1, Project o2) {
            return o1.cost - o2.cost;
        }
    }

    //利润大的排在前面的比较器
    public static class ProfitComparator implements Comparator<Project> {
        @Override
        public int compare(Project o1, Project o2) {
            return o2.profit - o1.profit;
        }
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<Project> costHeap = new PriorityQueue<>(new CostComparator());
        for (int i = 0; i < profits.length; i++) {
            costHeap.add(new Project(capital[i], profits[i]));
        }
        PriorityQueue<Project> profitHeap = new PriorityQueue<>(new ProfitComparator());
        for (int i = 0; i < k; i++) {
            while (!costHeap.isEmpty() && costHeap.peek().cost <= w) {
                profitHeap.add(costHeap.poll());//把小根堆里面能做的项目拿到大根堆
            }
            if (profitHeap.isEmpty()) {//如果小根堆的项目所需资金都大于启动资金w，那么没有项目可做，大根堆为空
                return w;
            }
            w += profitHeap.poll().profit;
        }
        return w;
    }
}