ภาพรวมปัญหา
บริษัท A ต้องการทำ IPO มีโครงการหลายโครงการ แต่ละโครงการมีกำไรสุทธิ Pi และต้องการทุนขั้นต่ำ Ci เริ่มต้นมีทุน W สามารถทำได้สูงสุด k โครงการ หาทุนสูงสุดหลังทำโครงการได้
ตัวอย่าง
k=2, W=0, Profits=[1,2,4], Capital=[0,1,1] → Output: 5
ทำโครงการ 0 (ต้องทุน 0) ได้กำไร 1 → ทุน=1, ทำโครงการ 2 (ต้องทุน 1) ได้กำไร 4 → ทุน=5
แนวทางแก้ปัญหา (Two Priority Queues)
- pqCapital: min-heap เรียงตาม Capital (โครงการที่ยังทำไม่ได้)
- pqMain: max-heap เรียงตาม Profit (โครงการที่ทำได้แล้ว)
- ซ้ำ k รอบ: ย้ายโครงการจาก pqCapital → pqMain ที่ Capital ≤ W, แล้ว pop pqMax เพิ่ม W
- ถ้า pqMain ว่าง → หยุด
ตัวอย่างโปรแกรม
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair<int, int> a, pair<int, int> b) {
return !(a.second < b.second); // min-heap by capital
}
};
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; // max-heap by profit
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;
}
};
int main() {
Solution ob;
vector<int> v = {1,2,4}, v1 = {0,1,1};
cout << (ob.findMaximizedCapital(2, 0, v, v1));
}
Input
2 0 [1,2,4] [0,1,1]
Output
5
