Home/

...

/

Maximize Capital (hard)

Maximize Capital (hard)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Maximize Capital (hard) lesson:

Press + to interact
Python 3.5
from heapq import *
def find_maximum_capital(capital, profits, number_of_projects, initial_capital):
  min_capital_heap = []
  max_profit_heap = []
  # insert all project capitals to a min-heap
  for i in range(0, len(profits)):
    heappush(min_capital_heap, (capital[i], i))
  # let's try to find a total of 'number_of_projects' best projects
  available_capital = initial_capital
  for _ in range(number_of_projects):
    # find all projects that can be selected within the available capital and insert them in a max-heap
    while min_capital_heap and min_capital_heap[0][0] <= available_capital:
      capital, i = heappop(min_capital_heap)
      heappush(max_profit_heap, (-profits[i], i))
    # terminate if we are not able to find any project that can be completed within the available capital
    if not max_profit_heap:
      break
    # select the project with the maximum profit
    available_capital += -heappop(max_profit_heap)[0]
  return available_capital
def main():
  print("Maximum capital: " +
        str(find_maximum_capital([0, 1, 2], [1, 2, 3], 2, 1)))
  print("Maximum capital: " +
        str(find_maximum_capital([0, 1, 2, 3], [1, 2, 3, 5], 3, 0)))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

Capital: [0, 1, 2]
Profits: [1, 2, 3]
number_of_projects: [2, 3]
initial_capital: 1

Iteration No.

Line No.

minCapitalHeap

maxProfitHeap

availableCapital

-

5-6

[]

[]

-

-

13

[(0, 0), (1, 1), (2, 2)]

[]

1

1

16-18

[(0, 0), (1, 1), (2, 2)]

[(-2, 1), (-1, 0)]

1

1

25

[(0, 0), (1, 1), (2, 2)]

[(-2, 1), (-1, 0)]

3

2

16-18

[(0, 0), (1, 1), (2, 2)]

[(-3, 2), (-1, 0)]

3

2

25

[(0, 0), (1, 1), (2, 2)]

[(-3, 2), (-1, 0)]

6

Sample Input #2

Capital: [0, 1, 2, 3]
Profits: [1, 2, 3, 5]
number_of_projects: [2, 3]
initial_capital: 0

Iteration No.

Line No.

minCapitalHeap

maxProfitHeap

availableCapital

-

5-6

[]

[]

-

-

13

[(0, 0), (1, 1), (2, 2), (3, 3)]

[]

0

1

16-18

[(0, 0), (1, 1), (2, 2), (3, 3)]

[(-1, 0)]

0

1

25

[(0, 0), (1, 1), (2, 2), (3, 3)]

[(-1, 0)]

1

2

16-18

[(0, 0), (1, 1), (2, 2), (3, 3)]

[(-2, 1)]

1

2

25

[(0, 0), (1, 1), (2, 2), (3, 3)]

[(-2, 1)]

3

3

16-18

[(0, 0), (1, 1), (2, 2), (3, 3)]

[(-5, 3), (-3, 2)]

3

3

25

[(0, 0), (1, 1), (2, 2), (3, 3)]

[(-5, 3), (-3, 2)]

8

Step-by-step solution construction

Let’s push all the capitals on to the min_capital_heap and initialize the available_capital to initial_capital.

Press + to interact
Python 3.5
from heapq import *
def find_maximum_capital(capital, profits, number_of_projects, initial_capital):
  min_capital_heap = []
  max_profit_heap = []
  # insert all project capitals to a min-heap
  for i in range(0, len(profits)):
    heappush(min_capital_heap, (capital[i], i))
  print("\t\tmin_capital_heap: " + str(min_capital_heap))
  # let's try to find a total of 'number_of_projects' best projects
  available_capital = initial_capital
  print("\t\tavailable_capital: " + str(available_capital))
  return available_capital
def main():
  capital = [[0, 1, 2],[0, 1, 2, 3]]
  profits = [[1, 2, 3],[1, 2, 3, 5]]
  number_of_projects = [2,3]
  initial_capital = [1,0]
  for i in range(len(capital)):
    print("Calculating maximum capital for: ")
    print("\tCapital: " + str(capital[i]))
    print("\tProfits: " + str(profits[i]))
    print("\tnumber_of_projects: " + str(number_of_projects[i]))
    print("\tinitial_capital: " + str(initial_capital[i]))
    print("Maximum Profit is: " + str(find_maximum_capital(capital[i], profits[i], number_of_projects[i],initial_capital[i])))
    print(("-"*100)+"\n")
    
main()

We need to find out the best number_of_projects projects; hence, we add a loop on line 16 in the code below.

On lines 18-20, we find all the projects from min_capital_heap that require a capital less than or equal to the available_capital and push them on to the max_profit_heap.

Press + to interact
Python 3.5
from heapq import *
def find_maximum_capital(capital, profits, number_of_projects, initial_capital):
  min_capital_heap = []
  max_profit_heap = []
  # insert all project capitals to a min-heap
  for i in range(0, len(profits)):
    heappush(min_capital_heap, (capital[i], i))
  print("\t\tmin_capital_heap: " + str(min_capital_heap))
  # let's try to find a total of 'number_of_projects' best projects
  available_capital = initial_capital
  print("\t\tavailable_capital: " + str(available_capital))
  for _ in range(number_of_projects):
    # find all projects that can be selected within the available capital and insert them in a max-heap
    while min_capital_heap and min_capital_heap[0][0] <= available_capital:
      capital, i = heappop(min_capital_heap)
      heappush(max_profit_heap, (-profits[i], i))
    print("\t\tmax_profit_heap: "+ str(max_profit_heap))
    
  return available_capital
def main():
  capital = [[0, 1, 2],[0, 1, 2, 3]]
  profits = [[1, 2, 3],[1, 2, 3, 5]]
  number_of_projects = [2,3]
  initial_capital = [1,0]
  for i in range(len(capital)):
    print("Calculating maximum capital for: ")
    print("\tCapital: " + str(capital[i]))
    print("\tProfits: " + str(profits[i]))
    print("\tnumber_of_projects: " + str(number_of_projects[i]))
    print("\tinitial_capital: " + str(initial_capital[i]))
    print("Maximum Profit is: " + str(find_maximum_capital(capital[i], profits[i], number_of_projects[i],initial_capital[i])))
    print(("-"*100)+"\n")
main()

Now, we have to get the projects that yield the maximum profit. Hence, we pop from the max_profit_heap and add the profit of that project to the available_capital on line 27.

We also add check to see if we even found any project to invest in, in the first place. If no such project is found, we break out of our loop.

Press + to interact
Python 3.5
from heapq import *
def find_maximum_capital(capital, profits, number_of_projects, initial_capital):
  min_capital_heap = []
  max_profit_heap = []
  # insert all project capitals to a min-heap
  for i in range(0, len(profits)):
    heappush(min_capital_heap, (capital[i], i))
  print("\t\tmin_capital_heap: " + str(min_capital_heap))
  # let's try to find a total of 'number_of_projects' best projects
  available_capital = initial_capital
  print("\t\tavailable_capital: " + str(available_capital))
  for _ in range(number_of_projects):
    # find all projects that can be selected within the available capital and insert them in a max-heap
    while min_capital_heap and min_capital_heap[0][0] <= available_capital:
      capital, i = heappop(min_capital_heap)
      heappush(max_profit_heap, (-profits[i], i))
    print("\t\tmax_profit_heap: "+ str(max_profit_heap))
    # terminate if we are not able to find any project that can be completed within the available capital
    if not max_profit_heap:
      break
    # select the project with the maximum profit
    available_capital += -heappop(max_profit_heap)[0]
    print("\t\tavailable_capital with the maximum profit: " + str(available_capital))
  return available_capital
def main():
  capital = [[0, 1, 2],[0, 1, 2, 3]]
  profits = [[1, 2, 3],[1, 2, 3, 5]]
  number_of_projects = [2,3]
  initial_capital = [1,0]
  for i in range(len(capital)):
    print("Calculating maximum capital for: ")
    print("\tCapital: " + str(capital[i]))
    print("\tProfits: " + str(profits[i]))
    print("\tnumber_of_projects: " + str(number_of_projects[i]))
    print("\tinitial_capital: " + str(initial_capital[i]))
    print("Maximum Profit is: " + str(find_maximum_capital(capital[i], profits[i], number_of_projects[i],initial_capital[i])))
    print(("-"*100)+"\n")
main()