Maximize Capital

Try to solve the Maximize Capital problem.

We'll cover the following

Statement#

A busy investor with an initial capital, c, needs an automated investment program. They can select k distinct projects from a list of n projects with corresponding capitals requirements and expected profits. For a given project ii, its capital requirement is capitals[i]capitals[i] , and the profit it yields is profits[i]profits[i].

The goal is to maximize their cumulative capital by selecting a maximum of k distinct projects to invest in, subject to the constraint that the investor’s current capital must be greater than or equal to the capital requirement of all selected projects.

When a selected project from the identified ones is finished, the pure profit from the project, along with the starting capital of that project is returned to the investor. This amount will be added to the total capital held by the investor. Now, the investor can invest in more projects with the new total capital. It is important to note that each project can only be invested once.

As a basic risk-mitigation measure, the investor wants to limit the number of projects they invest in. For example, if k is 22, the program should identify the two projects that maximize the investor’s profits while ensuring that the investor’s capital is sufficient to invest in the projects.

Overall, the program should help the investor to make informed investment decisions by picking a list of a maximum of k distinct projects to maximize the final profit while mitigating the risk.

Constraints:

  • 1≤1 \leq k ≤103\leq 10^3
  • 0≤0 \leq c ≤109\leq 10^9
  • 1≤1 \leq n ≤103\leq 10^3
  • k ≤\leq n
  • n ==== profits.length
  • n ==== capitals.length
  • 0≤0 \leq profits[i] ≤104\leq 10^4
  • 0≤0 \leq capitals[i] ≤109\leq 10^9

Examples#

Created with Fabric.js 3.6.6 1 2 2 3 2 4 6 8 Maximum capital = 11 Capitals Profits Sample example 1 n = 4, k = 2, c = 1

1 of 3

Created with Fabric.js 3.6.6 Capitals Profits 1 2 3 4 1 3 5 7 Sample example 2 Maximum capital = 17 n = 4, k = 3, c = 2

2 of 3

Created with Fabric.js 3.6.6 Maximum capital = 9 Capitals Profits 1 3 4 5 6 1 2 3 4 5 Sample example 3 n = 5, k = 3, c = 2

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Maximize Capital

1

What is the maximum capital for the following input?

k = 2

c = 1

capitals = [1, 2, 3]

profits = [2, 3, 5]

A)

6

B)

5

C)

8

D)

10

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create a min-heap to store capitals.

Identify the projects that can be invested within the range of the current capital.

Select the project that yields the highest profit.

Add the profit earned to the current capital.

Repeat until k projects have been selected.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided useful code templates in the other files that you may build on to solve this problem.

Python
usercode > main.py
Input #1
Input #2
Input #3
Input #4
%0 node_01 1 node_11 2 node_21 2 node_31 3
Visualization for Input #3
Maximize Capital

Two Heaps: Introduction

Solution: Maximize Capital