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

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

比如输入：

k=4           // 4个项目

W=20       // 本金20

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

10     8

100   60

输出

35

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

代码语言：javascript复制

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));
    }
}

cin int public static 数组

0 人点赞