Monto máximo de capital requerido para seleccionar como máximo K proyectos

Dado un número entero N , que representa el número de proyectos, dos arrays P[] y C[] , que constan de N números enteros, y dos números enteros W y K donde W es el monto de capital inicial, P[i] y C[i] son las utilidades y el capital requerido para elegir el i ^-ésimo proyecto . La tarea es calcular la cantidad máxima de capital requerida para elegir como máximo K proyectos , de modo que la ganancia de los proyectos elegidos se sume a W y elegir cualquier proyecto requiere al menos C[i] .

Ejemplos:

Entrada: N = 3, W = 0, K = 2, P[] = {1, 2, 3}, C[] = {0, 1, 1}
Salida: 4
Explicación:
Proyecto 1: Con la cantidad dada de W como 0, se puede elegir el proyecto 0 a un costo de C[0], es decir, 0, y después de terminar el capital agregado a W, es decir, W se convierte en W + P[0] = 1. ^Proyecto
2: con el valor dado cantidad de W como 1, el segundo ^proyecto se puede elegir a un costo de C[2], es decir, 1, y después de terminar el capital agregado a W, es decir, W se convierte en W + P[2] = 1 + 3 = 4.

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

Enfoque: el problema dado se puede resolver utilizando el algoritmo Greedy y la cola de prioridad . Siga los pasos a continuación para resolver el problema:

• Inicialice un PQ de cola de prioridad para almacenar todas las ganancias del proyecto cuyo capital es como máximo W .
• Recorre la array C[] usando la variable i como índice y empuja el par {C[i], i} en un vector de pares V .
• Ordena el vector V en orden ascendente con respecto al primer elemento .
• Iterar hasta que K sea mayor que 0 :
  • Empujar el beneficio de todos los proyectos que aún no han sido seleccionados y cuyo capital es como máximo W en la cola de prioridad PQ .
  • Incremente la cantidad de capital W por el elemento máximo de PQ , es decir, W += PQ.top() y luego extraiga el elemento superior de PQ .
  • Disminuya la K en 1 .
• Después de completar los pasos anteriores, imprima el valor de W como el capital máximo obtenido.

A continuación se muestra la implementación del enfoque anterior:

// 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 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.

4

Complejidad de Tiempo: O(N * K * log N)
Espacio Auxiliar: O(N)