C++의 IPO

한 회사 A가 곧 IPO를 시작하려고 한다고 가정해 보겠습니다. B에게 좋은 가격에 자신의 주식을 판매하기 위해 A는 IPO 전에 자본을 늘리는 몇 가지 프로젝트를 진행하려고 합니다. A는 제한된 자원을 가지고 있으며 IPO 전에 최대 k개의 개별 프로젝트만 완료할 수 있습니다. 최대 k개의 개별 프로젝트를 완료한 후 총 자본을 최대화하는 가장 좋은 방법을 설계하여 A를 도울 수 있습니까?

여러 프로젝트가 있다고 가정합니다. 각 프로젝트 i에 대해 순수 이익 Pi가 있고 해당 프로젝트를 시작하려면 Ci의 최소 자본이 필요합니다. 처음에는 W 캐피탈이 있습니다. 프로젝트가 완료되면 순수한 이익을 얻게 되며 이익은 총 자본에 추가됩니다.

요약하자면 주어진 프로젝트 목록에서 최대 k개의 개별 프로젝트 목록을 선택하여 최종 자본을 최대화하고 최종 최대 자본을 출력합니다.

따라서 입력이 − k =2, W =0이고 이익 목록이 [1,2,4]이고 자본이 [0,1,1]이면 출력은 5가 됩니다. 처음에는 자본이 0이므로 인덱스 0에서 프로젝트를 시작할 수 있으므로 이익 1을 얻을 수 있으므로 자본은 1이 됩니다. 자본이 1이면 인덱스 1 또는 2에서 프로젝트를 시작할 수 있으며 인덱스 2에서 프로젝트를 선택하여 더 많은 이익을 얻으므로 최종 답은 0 + 1 + 4 =5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 우선순위 큐 pqCapital 및 pqMain 생성
• n :=이익 규모
• 초기화 i의 경우:=0, i
• pqCapital에 { Profits[i], Capital[i] } 삽입

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
struct Comparator{
   bool operator() (pair <int, int> a, pair <int, int> b){
      return !(a.second < b.second);
   }
};
class Solution {
public:
   int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
   priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator> pqCapital;
   priority_queue < pair <int ,int> > pqMain;
   int n = Profits.size();
   for(int i = 0; i < n; i++){
      pqCapital.push({Profits[i], Capital[i]});
   }
   for(int i = 0; i < k; i++){
      while(!pqCapital.empty() && pqCapital.top().second <= W){
         pqMain.push(pqCapital.top());
         pqCapital.pop();
      }
      if(pqMain.empty()) break;
         W += pqMain.top().first;
         pqMain.pop();
      }
      return W;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,4}, v1 = {0,1,1};
   cout << (ob.findMaximizedCapital(2,0, v, v1));
}

입력

2
0
[1,2,4]
[0,1,1]

출력

5