Greedy Algorithms8 sections · 316 units
Open in Course

Problem - IPO

Maximize capital

You have initial capital WW and can complete at most kk projects. Each project has a profit and a minimum capital required. After completing a project, your capital increases by its profit. Maximize final capital. For k=2k=2, W=0W=0, profits=[1,2,3]profits=[1,2,3], capital=[0,1,1]capital=[0,1,1], the answer is 44. Do project 00 (profit 11, now have 11), then project 22 (profit 33, now have 44).

Here's a two-constraint greedy problem.

You need enough capital to start, then you want maximum profit.