Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >项目获得的最大收益(贪心)

项目获得的最大收益(贪心)

作者头像
砖业洋__
发布于 2023-05-06 08:53:30
发布于 2023-05-06 08:53:30
14600
代码可运行
举报
文章被收录于专栏:博客迁移同步博客迁移同步
运行总次数:0
代码可运行

大意是这样:有k个项目,你的本金是W,然后每次只能串行做一个项目,不能并行,输入每个项目需要的资金以及做完后获得的利润,每做完一个项目,马上获得的利润,可以支持你去做下一个项目,求最后获得的最大利润。

比如输入:

k=4           // 4个项目

W=20       // 本金20

5       7     // 需要的资金和利润

10     8

100   60

输出

35

思路:做完项目就停止,或者做到没有足够本金去做下一个项目时停止

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import java.io.BufferedInputStream;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class test {
    public static int[] pro = new int[100]; // 假设会议不超过100个,如果需要更多就把数组开大一点
    public static int[] cost = new int[100];

    public static class Node {
        public int pro, cost;

        public Node(int cost, int pro) {
            this.pro = pro;
            this.cost = cost;
        }
    }

    public static int maxMoney(int k, int W, int[] cost, int[] pro) {
        PriorityQueue<Node> maxproPQ = new PriorityQueue<Node>(new Comparator<Node>() { 
        // 最大利润堆
            @Override
            public int compare(Node o1, Node o2) {
                return o2.pro - o1.pro;
            }
        });
        PriorityQueue<Node> mincostPQ = new PriorityQueue<Node>(new Comparator<Node>() {
        // 最小花费堆
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });

        for (int i = 0; i < k; ++i) {
            mincostPQ.add(new Node(cost[i], pro[i]));
        }

        for (int i = 0; i < k; ++i) { // 依次做k个项目,每次只能做一个
            while (!mincostPQ.isEmpty() && mincostPQ.peek().cost <= W) { // 如果小顶堆空了说明项目做完了,
                // 如果小顶堆最上面那个花费最小的项目已有的资金还是做不了,那么就做不了,
                // 去大顶堆做其他项目多得点利润,这样看能不能开启下一个项目做
                maxproPQ.add(mincostPQ.poll());
            }
            if (maxproPQ.isEmpty()) { // 大顶堆为空说明能做的已经做完了
                return W;
            }
            W += maxproPQ.poll().pro; // 加上利润,有可能会开启下一个项目
        }
        return W;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int k = cin.nextInt(); // k个项目要做
        int W = cin.nextInt(); // 项目初始资金
        for (int i = 0; i < k; ++i) {
            cost[i] = cin.nextInt(); // 项目需要花费的初始资金
            pro[i] = cin.nextInt(); // 项目的利润
        }
        cin.close();
        System.out.println(maxMoney(k, W, cost, pro));
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-03-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Expedition(优先队列)
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; /** * Expedition 你需要驾驶一辆卡车行驶L单位距离。最开始时,卡车上有P单位的汽油。卡车上每开1单位距离需要消耗1单位的汽油。 * 如果在途中车上的汽油耗尽,卡车就无法继续前行,因而无法到达终点。在途中一共有N个加油站。 * 第i个加油站在距离起点Ai单位的地方,最
砖业洋__
2023/05/06
1320
CodeForces E. XOR and Favorite Number(Div.2)
 一个莫队的基础题,题目要求[L,R]里面有多少对子区间异或值为k,记录一下前缀异或和arr,因为x^x=0,现在我们要求区间[L,R]的异或和值,用arr数组表示就是arr[L-1]^arr[R]==k,或者说arr[R]^k==arr[L-1]
mathor
2018/09/19
2830
CodeForces E. XOR and Favorite Number(Div.2)
CodeForces D.Powerful array(Div.1)
 大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,实在是没办法了,用c过的,就改一下莫队的remove和add函数即可
mathor
2018/09/19
3600
CodeForces D.Powerful array(Div.1)
<贪心>会议室宣讲&&哈弗曼树&&切金条&&LeetCode502IPO
一些项目要占用一个会议室宣讲, 会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组, 里面 是一个个具体的项目), 你来安排宣讲的日程, 要求会议室进行 的宣讲的场次最多。 返回这个最多的宣讲场次。
大学里的混子
2019/02/21
6250
赚最多的钱 --贪心算法
输入: 参数1,正数数组costs 参数2,正数数组profits 参数3, 正数k 参数4,正数m costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花 费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多做k个项目 m表示你初始的资金 说明:你每做完一个项目,马上获得的收益,可以支持你去做下 一个 \项目。 输出: 你最后获得的最大钱数
名字是乱打的
2022/05/13
3520
赚最多的钱 --贪心算法
安排会议(区间问题、贪心)
   题目: 一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组,里面是一个个具体的项目),你来安排宣讲的日程,要求会议室进行 的宣讲的场次最多。输出这个最多的宣讲场次。
砖业洋__
2023/05/06
2110
安排会议(区间问题、贪心)
区间调度问题(贪心)
/*区间调度问题 * 有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参加与否。 * 如果选择了参加,那么自始至终都必须全程参加。此外,参加工作的时间段不能重叠(即使是开始的瞬间 * 和结束的瞬间的重叠也是不允许的)。 * 你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢? * 限制条件: * 1≤N≤100000 * 1≤si≤ti≤10的9次方 * */ import java.util.Collections; import java.ut
砖业洋__
2023/05/06
1570
L2-009. 抢红包
没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录,请你统计一下他们抢红包的收获。
砖业洋__
2023/05/06
3400
L2-009. 抢红包
挑战程序竞赛系列(7):2.1一往直前!贪心法(区间)
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72675265
用户1147447
2019/05/26
3850
切金条(哈夫曼、贪心)
这里用到的是哈夫曼编码原理,关于这个知识点的讲解可以看这位博主的,我觉得写的很好点击打开链接
砖业洋__
2023/05/06
1260
挑战程序竞赛系列(3):2.3需要思考的动规
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71475303
用户1147447
2019/05/26
4640
挑战程序竞赛系列(12):2.5最小生成树
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/73469965
用户1147447
2019/05/26
3420
堆(优先级队列 PriorityQueue)
GeekLiHua
2025/01/21
980
堆(优先级队列 PriorityQueue)
区间合并(c++,java)
给定一个长度为 n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
GeekLiHua
2025/01/21
520
leetcode502. IPO
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
眯眯眼的猫头鹰
2020/05/11
4510
Java实现操作系统实验之磁盘调度
这一版的磁盘调度,作者只分析了磁盘通道号,之后作者会加入对最晚完成时间的分析。 首先理解一下,什么是磁盘调度,磁盘调度的意思是,所有的进程都是在磁盘中得某个同道号中享受资源的,那么就会存在一个问题,我们是按什么顺序来执行这些进程呢,
萌萌哒的瓤瓤
2020/08/26
7570
挑战程序竞赛系列(1):2.3动态规划
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71091333
用户1147447
2019/05/26
3120
挑战程序竞赛系列(9):2.4优先队列
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72773026
用户1147447
2019/05/26
3390
小和问题(归并排序的例子)
小和问题 在一个数组中, 每一个数左边比当前数小的数累加起来, 叫做这个数组的小和。 求一个数组 的小和。 例子: [1,3,4,2,5] 1左边比1小的数, 没有; 3左边比3小的数, 1; 4左边比4小的数, 1、 3; 2左边比2小的数, 1; 5左边比5小的数, 1、 3、 4、 2;
砖业洋__
2023/05/06
2060
小和问题(归并排序的例子)
L2-023. 图着色问题
图着色问题是一个著名的NP完全问题。给定无向图 G = (V, E),问可否用K种颜色为V中的每一个顶点分配一种颜色,使得不会有两个相邻顶点具有同一种颜色?
砖业洋__
2023/05/06
2300
L2-023. 图着色问题
相关推荐
Expedition(优先队列)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档