贪心策略：请你挑选k个项目，使得自己耗费成本最低，赚的利润最多

贪心策略：请你挑选k个项目，使得自己耗费成本最低，赚的利润最多

提示：从本文开始，咱们来说贪心策略系列文章！！

贪心策略在互联网大厂的招聘笔试和面试中的地位！！！在笔试中考贪心，而面试不考贪心。

（1）贪心在笔试中：75%的考题都是贪心策略，为啥呢，一方面考你的聪明程度，另一方面，考你的代码编写能力；所以我参加过的笔试证明了这一点，往往大厂给你三个算法题，第1道题一定是贪心，排序结合的算法题，你需要懂点脑子，了解一下排序和堆啥的数据结构，还得会点贪心技巧，才能设计出来；
（2）面试不怎么考贪心策略，为什么？因为面试考你的是算法的优化能力，所以如果给你贪心的话，你一下子想到了解决方案，也不谈什么优化的事情，没意义，所以不考贪心。
（3）你必须要认识到：最简单的是国内的面试过程（嘴说的事情，都好办），难度中上等的是国外的笔试面试，最难的国内的算法笔试。 那么，你一定要明白，最难的还是国内的算法笔试题！！！因此要多练，多学，多见题，多思考，多总结，才能拿下。

以下是贪心策略基础题目系列文章：
（1）贪心策略：请你计算i×arr[i]的累加和最大值
（2）贪心策略：请你设计最优的安排会议日程表，以使得举行的会议数最多
（3）贪心策略：求一条街上最少应该放多少盏灯，才能照亮整条街的商户
（4）贪心策略：请你将字符串拼接，最终拼接好的字符串字典序最小
（5）贪心策略：请你最最小的金条分割代价
（6）贪心策略：不断循环 *** 作数组arr中的任意两个数，当只剩下1个数，返回这个数可能的最大值

今天说一些，本贪心系列文章的最后一篇

---

文章目录

• 贪心策略：请你挑选k个项目，使得自己耗费成本最低，赚的利润最多
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 总结

题目

LeetCode的题目：
请你挑选k个项目，使得自己耗费成本最低，赚的利润最多

给手里的启动资金M，我最多只能做K个项目，而且是先做完一个才能接下一个，不能同时进行俩
cost数组是我的多个项目的成本，profit数组是我多个项目的收益，即净利润，
实际上做完这个项目后，我手里的钱为M+profit，这是我下一个项目的启动资金【不考虑耗费的成本，只是有这个钱能干这个活】

请问完成k个项目后你最后的钱数是多少？？

---

一、审题

示例：比如
cost=1,1,4,5
profit=3,1,3,2
M=1,K=2
既然启动资金为1，我就只能从1成本的俩项目中选择，显然，我们贪心的商人
一定会选择更低的成本和收益更高的项目，很自然，很明了，商人追逐最大利润，没什么坏心思，即选了第一个项目
最后我的第二次启动资金就是M+=profit=1+3=4
第二次我的启动资金只够4，就收入3那个，所以最后我的钱：M+=3=4+3=7

---

二、解题

上面也说了，咱不考虑耗费成本，只考虑我手里赚了多少钱
启动资金+赚的利润，就是我最后的钱

贪心策略：很自然，追逐利益
考虑成本小的项目，只做利润高的——当然，前提是你的启动资金要够本，才能去干
所以呢？
项目为固定的类

 //数据为项目类型--用来放堆里的
    public static class Program{
        public int c;//成本
        public int p;//收益
        public Program(int cc, int pp){
            c = cc;
            p = pp;
        }
    }

比如：

贪心策略的实现过程：
（1）2个堆，一个小根堆heapCost，最开始让项目按照成本升序排
（2）每次做谁呢？
你只能干启动资金够得着成本堆heapCost的那些项目，全部从小根堆中d出来，进入大根堆heapProfit
（3）这样，我们从大根堆heapProfit中d出那个利益最大的来做。
（4）最多做k个，一旦某一次无法启动，今后没得玩（大根堆是空的，那你带着本金走人吧，干不了）

k=2个：只能做俩
（1）第一个：
最开始1块钱启动资金m=1
能做谁？前面俩项目
但是利润3多的肯定先做了，得到本金m=1+3=4

（2）第二个，由于4又能启动第三个项目，就把它放入大根堆，显然，利润高的做了。就是4这个
所以启动资金又变为m=4+3=7

此时俩任务目标做完。返回总得钱数7。

2个堆的比较器：

//两个比较器，一个按照cost排序，小根堆，升序
    public static class costComparator implements Comparator<Program>{
        @Override
        public int compare(Program o1, Program o2){
            return o1.c - o2.c;
        }
    }

    //两个比较器，一个按照profit排序，大根堆，降序
    public static class profitComparator implements Comparator<Program>{
        @Override
        public int compare(Program o1, Program o2){
            return o2.p - o1.p;
        }
    }

然后玩项目，赚钱

//复习：用2个堆搞定
    public static int maxMoney(int[] cost, int[] profit, int M, int K){
        if (K == 0) return 0;

        //准备俩堆
        PriorityQueue<Program> heapCost = new PriorityQueue<>(new costComparator());
        PriorityQueue<Program> heapProfit = new PriorityQueue<>(new profitComparator());

        //先把项目装入小根堆，按照cost升序
        for (int i = 0; i < cost.length; i++) {
            Program p = new Program(cost[i], profit[i]);
            heapCost.add(p);
        }

        //然后看看你的启动资金做K个项目OK吗
        for (int i = 0; i < K; i++) {

            //最开始看看你能启动哪些，能就启动，然后做收益最高的那个
            while (!heapCost.isEmpty() && heapCost.peek().c <= M){
                heapProfit.add(heapCost.poll());//转移
            }

            //然后做最大利润
            if (heapCost.isEmpty()) return M;//压根你就没法启动一个项目的话，不好意思，带着本金走人
            //只有有项目可以干，必定干了
            M += heapProfit.poll().p;//d出这个任务，干了收钱，我们只看收益，成本已经考虑进去了。
        }

        return M;
    }

    public static void test(){
        int[] cost= {1,1,4,5};
        int[] profit = {3,1,3,2};
        int M = lessCMoreP(1, 2, cost, profit);
        System.out.println(M);

        M = maxMoney(cost, profit, 1, 2);
        System.out.println(M);
    }

    public static void main(String[] args) {
        test();
    }

验证：

7
7

行，贪心系列文章就到此，基础打好，知道有贪心，该怎么应对就行。

---

总结

提示：重要经验：

1）老话，贪心题目，多见题，多练习，多总结，培养敏感度！
2）本题就是在自然不过的贪心了，商人逐利，以最低成本，赚最多的利润。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。