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 ith 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 0th 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 2nd 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 projectsint 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 Codeint 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 approachimport 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 projectsdef 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 = 2W = 0P = [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 projectsfunction 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 approachusing 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 SortedSetpublic 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:Â
4
Â
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
