Let’s say LeetCode is about to launch an IPO. In order to sell the shares to venture capital firms at a higher price, Lico hopes to carry out projects to boost its capital before the IPO. With limited resources, it can only complete a maximum of K different projects before the IPO. Help Lico design the way to get the maximum total capital after completing up to K different projects.

I give you n items. For each project I, there is a net profit [I] and the minimum capital[I] required to start the project.

Initially, your capital was W. When you complete a project, you will make a net profit and the profit will be added to your total capital.

In summary, select a list of up to K different projects from a given project to maximize the final capital and output the maximum capital ultimately available.

The answer is guaranteed to be in the range of 32 – bit signed integers.

Example 1:

Profits = 0, capital = [0,1, 2], capital = [0,1,1] At the end of that, you’ll make a profit of 1, and your total capital will be 1. At this point you can choose to start project 1 or 2. Since you can choose up to two projects, you need to complete project 2 to get the most capital. So the final maximum capital output is 0 + 1 + 3 = 4.

Source: LeetCode

Read the topic

  1. Limit yourself to k different projects
  2. Do not spend money, only see their own money enough to cost. w >= capital[i]

Requirements: maximum ultimate holding capital.

Read the topic, on a feeling, to stem to stem the most can make money, this is not let me greedy? Dude, go for it…

Their thinking

Tell me a story

You are the CEO of LeetCode, heading for a peak IPO, and you need to make as much money as possible in a limited number of projects in order to drive up the stock price and earn as much CAI.

Your initial capital is W, so you get nothing for nothing. Note that your capital w needs to be >= the cost of the project you want to work on, which can only be done once.

  1. First of all, you can only work on k projects. You have to work on the most profitable project every time, so that your capital w grows, and the more capital you hold, the bigger and more profitable the project.
  2. All right, let’s take the first shot, and we need to pick the most profitable of all possible projects. What do we do? Sort projects from small to large in terms of capital requirements. Then work on the most profitable project. We worked on the most profitable project, got nothing for nothing. At the same time, our initial assets + this first vote earned money, holding capital growth, it must quickly look for the next most profitable.
  3. And then you do it just like you did the first one, until you do k.
  4. Done, the ultimate maximum amount of capital you hold as interim CEO.
Back at the code level
  1. The above story tells us to rank the amount of money needed for a project from the smallest to the largest.
  2. Use a priority queuepriority_queue<int> qIn each cycle, the profit of the project whose required capital is less than the capital held w is put into priority queue Q and sorted automatically. Update w each time you take top() of q. And then do this k times.

Greed is just like this: each small phase is locally optimal, and then you can push to global optimal. Just like in this case, the one that makes the most money each time you do it, you end up with the most capital.

PS:

  • Q:C + + the sort ofvector<pair<int, int>>Compare pair.first first, then pair.second?
  • A: std::sortYou don’t have to write a comparison function, you don’t have to write a sort functionoperator<To compare. whilestd::pair::operator<By standard, the first of two STD :: pairs is the first priority and the second is the second priority.
template <class _Ty1.class _Ty2>
_NODISCARD constexpr bool operator< (const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right) {
    return_Left.first < _Right.first || (! (_Right.first < _Left.first) && _Left.second < _Right.second); }Copy the code

code

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        vector<pair<int.int>> info;
        int size = profits.size(a);for(int i = 0; i < size; i++) {
            info.push_back({capital[i], profits[i]});
        }

        sort(info.begin(), info.end());
        priority_queue<int> q;
        int idx = 0, iSize = info.size(a);while(k--){
            while(idx < iSize && w >= info[idx].first) {
                q.push(info[idx++].second); 
            }
            if(q.empty()) {
                break; 
            }else {
                w += q.top(a); q.pop();
            }
        }
        returnw; }};Copy the code

Supplement & acknowledgement

Thank you very much for the code Catalog. This brother’s Leetcode is classified into different algorithm types and has different language versions, which is of great help to me as a vegetable chicken.

In addition, I also complete a brush notes, adhere to the Feynman method of learning, eat, produce.

If you feel the solution of this problem is helpful to you, please do not hesitate to like 👍🏻 ah rush rush…