Maximum amount of capital required for selecting at most K projects

0 0 6 minutes read

Given an integer N, representing number of projects, two arrays P[] and C[], consisting of N integers, and two integers W and K where, W is the initial capital amount, P[i] and C[i] are the profits and capital required to choose the i^th project. The task is to calculate the maximum amount of capital required to choose at most K projects, such that the profit of the chosen projects is added to W and choosing any project required at least C[i].

Examples:

Input: N = 3, W = 0, K = 2, P[] = {1, 2, 3}, C[] = {0, 1, 1}
Output: 4
Explanation:
Project 1: With the given amount of W as 0, the 0^th project can be chosen at a cost of C[0] i.e., 0, and after finishing the capital added to W i.e., W becomes W + P[0] = 1.
Project 2: With the given amount of W as 1, the 2^nd project can be chosen at a cost of C[2] i.e., 1, and after finishing the capital added to W i.e., W becomes W + P[2] = 1 + 3 = 4.

Input: N = 3, W = 1, K = 1, P[] = {10000, 2000, 3000}, C[] = {1, 1, 1}
Output: 10001

Approach: The given problem can be solved using the Greedy Algorithm and priority queue. Follow the steps below to solve the problem:

Initialize a priority_queue PQ to store all the project’s profit whose capital is at most W.
Traverse the array C[] using the variable i as the index and push the pair {C[i], i} in a vector of pairs V.
Sort the vector V in ascending order with respect to the first element.
Iterate until K is greater than 0:
- Push profit of all the projects that have not been selected yet and whose capital is at most W in the priority queue PQ.
- Increment the capital amount W by the maximum element of PQ i.e., W += PQ.top() and then pop the top element of PQ.
- Decrement the K by 1.
After completing the above steps, print the value of W as the maximum capital obtained.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate maximum capital
// obtained after choosing at most K
// projects whose capital is less than
// the given cost of projects
int maximizedCapital(int K, int W,
                     vector<int>& profits,
                     vector<int>& capital)
{
    // Stores all projects with
    // capital at most W
    priority_queue<int> pq;
 
    // Stores the pair of {C[i], i}
    vector<pair<int, int> > v;
 
    // Traverse the vector C[]
    for (int i = 0;
         i < capital.size(); i++) {
        v.push_back({ capital[i], i });
    }
 
    // Sort the vector v
    sort(v.begin(), v.end());
 
    int j = 0;
 
    while (K) {
 
        // If capital is at most W
        while (j < (int)capital.size()
               && v[j].first <= W) {
 
            // Push the profit into
            // priority queue
            pq.push(profits[v[j].second]);
 
            // Increment j by one
            j++;
        }
 
        // If pq is not empty
        if (!pq.empty()) {
 
            // Update the capital W
            W = W + pq.top();
 
            // Delete the top of pq
            pq.pop();
        }
 
        // Decrement K by one
        K--;
    }
 
    // Return the maximum capital
    return W;
}
 
// Driver Code
int main()
{
    int K = 2;
    int W = 0;
    vector<int> P = { 1, 2, 3 };
    vector<int> C = { 0, 1, 1 };
    cout << maximizedCapital(K, W, P, C);
 
    return 0;
}

Java

// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
 
    // Function to calculate maximum capital
    // obtained after choosing at most K
    // projects whose capital is less than
    // the given cost of projects
    static int maximizedCapital(int K, int W, int profits[],
                                int capital[])
    {
        // Stores all projects with
        // capital at most W
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            Collections.reverseOrder());
 
        // Stores the pair of {C[i], i}
        ArrayList<int[]> v = new ArrayList<>();
 
        // Traverse the vector C[]
        for (int i = 0; i < capital.length; i++) {
            v.add(new int[] { capital[i], i });
        }
 
        // Sort the vector v
        Collections.sort(v, (a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            return a[1] - b[1];
        });
 
        int j = 0;
 
        while (K != 0) {
 
            // If capital is at most W
            while (j < capital.length && v.get(j)[0] <= W) {
 
                // Add the profit into
                // priority queue
                pq.add(profits[v.get(j)[1]]);
 
                // Increment j by one
                j++;
            }
 
            // If pq is not empty
            if (!pq.isEmpty()) {
 
                // Update the capital W
                W = W + pq.peek();
 
                // Delete the top of pq
                pq.poll();
            }
 
            // Decrement K by one
            K--;
        }
 
        // Return the maximum capital
        return W;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int K = 2;
        int W = 0;
        int P[] = { 1, 2, 3 };
        int C[] = { 0, 1, 1 };
       
        System.out.println(maximizedCapital(K, W, P, C));
    }
}
 
// This code is contributed by Kingash.

Python3

from queue import PriorityQueue
 
# Function to calculate maximum capital
# obtained after choosing at most K
# projects whose capital is less than
# the given cost of projects
def maximized_capital(k, w, profits, capital):
    # Stores all projects with
    # capital at most W
    pq = PriorityQueue()
 
    # Stores the pair of , i]
    v = []
 
    # Traverse the vector C[]
    for i in range(len(capital)):
        v.append([capital[i], i])
 
    # sort the vector
    v.sort()
 
    j = 0
 
    while k:
        # if the capital is at most w
        while j < int(len(capital)) and v[j][0] <= w:
            # push the profit into 
            # priority queue
            pq.put(-profits[v[j][1]])
             
            # increment the j by 1
            j += 1
 
        # If pq i not empty 
        if pq.empty() is not True:
            temp = pq.get()
            # Update the capital w and go for next
            w = w + abs(temp)
         
        # Decrement k by 1
        k -= 1 
     
    # return the maximum capital
    return w
 
K = 2
W = 0
P = [1, 2, 3]
C = [0, 1, 1]
print(maximized_capital(K, W, P, C))
 
# This code is contributed by sdeadityasharma.

Javascript

// Function to calculate maximum capital
// obtained after choosing at most K
// projects whose capital is less than
// the given cost of projects
function maximized_capital(k, w, profits, capital) 
{
 
  // Stores all projects with capital at most W
  const pq = [];
 
  // Stores the pair of , i]
  const v = [];
 
  // Traverse the vector C[]
  for (let i = 0; i < capital.length; i++) {
    v.push([capital[i], i]);
  }
 
  // sort the vector
  v.sort((a, b) => a[0] - b[0]);
 
  let j = 0;
 
  while (k) {
    // if the capital is at most w
    while (j < capital.length && v[j][0] <= w) {
      // push the profit into priority queue
      pq.push(-profits[v[j][1]]);
 
      // increment the j by 1
      j++;
    }
 
    // If pq is not empty
    if (pq.length) {
      const temp = pq.pop();
      // Update the capital w and go for next
      w = w + Math.abs(temp);
    }
 
    // Decrement k by 1
    k--;
  }
 
  // return the maximum capital
  return w;
}
 
const K = 2;
const W = 0;
const P = [1, 2, 3];
const C = [0, 1, 1];
console.log(maximized_capital(K, W, P, C));
 
// This code is contributed by Aditya Sharma

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class Program
{
    // Function to calculate maximum capital
    // obtained after choosing at most K
    // projects whose capital is less than
    // the given cost of projects
    public static int MaximixedCapital(int K, int W, List<int> profits, List<int> capital)
    {
        // Stores all projects with
        // capital at most W
        PriorityQueue<int> pq = new PriorityQueue<int>();
 
        // Stores the pair of , i]
        List<List<int>> v = new List<List<int>>();
 
        // Traverse the vector C[]
        for (int i = 0; i < capital.Count; i++)
        {
            List<int> temp = new List<int>();
            temp.Add(capital[i]);
            temp.Add(i);
            v.Add(temp);
        }
 
        // Sort the vector v
        v.Sort((a, b) => a[0].CompareTo(b[0]));
 
        int j = 0;
 
        while (K > 0)
        {
            // If the capital is at most W
            while (j < capital.Count && v[j][0] <= W)
            {
                // Push the profit into 
                // priority queue
                pq.Push(-profits[v[j][1]]);
                 
                // Increment j by 1
                j += 1;
            }
 
            // If pq is not empty 
            if (pq.Count != 0)
            {
                // Update the capital W and go for next
                W = W + Math.Abs(pq.Pop());
            }
 
            // Decrement K by 1
            K -= 1;
        }
 
        // Return the maximum capital
        return W;
    }
 
    public static void Main()
    {
        int K = 2;
        int W = 0;
        List<int> P = new List<int> { 1, 2, 3 };
        List<int> C = new List<int> { 0, 1, 1 };
        Console.WriteLine(MaximixedCapital(K, W, P, C));
    }
}
 
// PriorityQueue implementation using SortedSet
public class PriorityQueue<T> where T : IComparable<T>
{
    private SortedSet<T> data;
 
    public PriorityQueue()
    {
        data = new SortedSet<T>();
    }
 
    public void Push(T item)
    {
        data.Add(item);
    }
 
    public T Pop()
    {
        T item = data.Min;
        data.Remove(item);
        return item;
    }
 
    public int Count
    {
        get { return data.Count; }
    }
}
 
// This code is contributed by princekumaras

Output:

Time Complexity: O(N * K * log N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!