算法-贪心-做项目获得最大收益

2022-4-18 diaba 算法 

package com.jiucaiyuan.net.question;

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

/**
 * 【问题】做一个项目，有成本，也有利润，一堆项目，如何选择做，实现收益最大？
 * 【思路】把所有项目，按照成本放入小根堆，从小根堆中拿出可以做的项目，然后按照利润放入大跟堆，开始先做大根堆的对顶项目
 *
 * @Author jiucaiyuan  2022/4/18 23:10
 * @mail services@jiucaiyuan.net
 */
public class MaxProfits {
    public static class Node {
        public int cost;
        public int profit;

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

    public static class MinCostComparator implements Comparator<Node> {
        @Override
        public int compare(Node node1, Node node2) {
            return node1.cost - node2.cost;
        }
    }

    public static class MaxProfitComparator implements Comparator<Node> {
        @Override
        public int compare(Node node1, Node node2) {
            return node2.profit - node1.profit;
        }
    }

    /**
     * 没做完一个项目，马上获得收益，可以支持继续做下一个项目，输出最后获得的最大钱数
     *
     * @param k       只能串行，最多做k个项目
     * @param w       初始资金
     * @param profits profits[i]是i号项目扣除成本后还能剩下的钱（利润）
     * @param costs   costs[i]是i号项目的花费
     * @return
     */
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] costs) {
        PriorityQueue<Node> minCostQueue = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> maxProfitQueue = new PriorityQueue<>(new MaxProfitComparator());
        //所有项目扔到锁定池中，按照花费组织的小根堆
        for (int i = 0; i < profits.length; i++) {
            minCostQueue.add(new Node(costs[i], profits[i]));
        }
        for (int i = 0; i < k; i++) {  //进行k轮
            //能力所及的项目，全部解锁
            while (!minCostQueue.isEmpty() && minCostQueue.peek().cost < w) {
                maxProfitQueue.add(minCostQueue.poll());
            }
            if (maxProfitQueue.isEmpty()) {
                return w;
            }
            w += maxProfitQueue.poll().profit;
        }
        return w;
    }

    public static void main(String[] args) {
        int[] profits = {1, 2, 3, 5, 3, 2, 1, 4, 54, 5};
        int[] costs = {1, 1, 1, 1, 1, 12, 2, 1, 2, 1};
        System.out.println(findMaximizedCapital(10, 5, profits, costs));
    }
}

« 算法-N皇后问题（含加速版本） | 算法-贪心-会议安排问题»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022