java贪心算法经典案例之项目利润最大问题
2021/5/13 12:27:21
本文主要是介绍java贪心算法经典案例之项目利润最大问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、问题描述
输入:
正数数组costs
正数数组profits
正数k
正数m
含义:
costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
k表示你只能串行的最多做k个项目
m表示你初始的资金
说明:
你每做完一个项目,马上获得的收益,可以支持你去做下一个项目。
输出:
你最后获得的最大钱数。
2、问题分析
该问题很明显是一个贪心相关的问题,我们每次做项目的时候都选择项目成本在我的启动资金之内,并且利润最大的项目来做,这样是不是就做到了项目的利润最大化。
这里我们考虑使用两个堆来完成该贪心算法:一个大根堆(按项目利润组织)
,一个小根堆(按项目花费组织的)
①、首先将每个项目的启动资金(花费)和该项目的利润组成一个个的节点
②、将第一步组成的节点添加到一个小根堆里(添加完成后该小根堆就不动了,仅供每次从这个小根堆里挑选项目)。
③、每次挑一个在我们启动资金范围内且利润最大的项目。最多做k个项目,每次挑一个项目做,则我们需要挑的项目一定是花费在我们启动资金以内,并且他的利润一定是最大的。所以我们每次挑项目的时候:
1、首先根据我们的现有启动资金,从小根堆里挑选出所有项目成本小于我们的启动资金的项目。
2、将挑出来的项目全部放入到一个大根堆里(按利润组织的)
3、然后从大根堆里拿出堆顶项目(该项目就是满足项目成本在启动资金内,且利润最大的项目)
4、累加上面的项目所获得的利润。继续挑选下一个项目
3、代码实现
/** * 贪心算法求做项目最大利润问题 * * @param k 最多能做的项目数量 * @param w 启动资金 * @param profits 每个项目的利润 * @param capital 每个项目的成本 * @return: int */ public static int findMaximizedCapital(final int k, int w, final int[] profits, final int[] capital) { // 小根堆,按照每个项目的最小花费(成本)构建成小根堆 final PriorityQueue<Node> minCostQueue = new PriorityQueue<>(); // 大根堆,按照每个项目的利润构建成一个大根堆 final PriorityQueue<Node> maxProfitQueue = new PriorityQueue<>(); // 先将每个项目的成本和利润组织为一个个的节点并放入到小根堆中 for (int i = 0; i < profits.length; i++) { minCostQueue.add(new Node(profits[i], capital[i])); } // 开始做项目,每次循环代表做一个项目 for (int i = 0; i < k; i++) { // 取出我当前启动资金能做的所有项目(即:项目成本小于我的启动资金的项目),放入到大根堆中 // 注意这里peek和poll的区别,peek 不会删除元素,poll 会删除元素 while (!minCostQueue.isEmpty() && minCostQueue.peek().cost <= w) { maxProfitQueue.add(minCostQueue.poll()); } // 这里需要特别注意,很容易被忽视掉 // 如果 maxProfitQueue 为空,则表示按照当前的启动资金,已经没有办法从小根堆(minCostQueue)里取出任何一个项目来做了 if (maxProfitQueue.isEmpty()) { return w; } // 每次挑一个项目成本在我启动范围之内,并且利润最大的项目做 final Node project = maxProfitQueue.poll(); // 每个项目做完后,启动资金增加 w = w + project.profit; } return w; }
这篇关于java贪心算法经典案例之项目利润最大问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?