Dado un saco de capacidad W, y dos arrays A[] y B[] de longitud N , donde A[i] representa el peso de un i -ésimo bloque de oro y B[i] representa la ganancia obtenida al tomar el i -ésimo bloque de oro, la tarea es encontrar la ganancia máxima obtenida al tomar una parte o la totalidad de un bloque de oro con un peso cuadrado no perfecto, que no exceda la capacidad del saco.
Ejemplos:
Entrada: A[]= {4, 5, 7}, B[] = {8, 5, 4), W = 10
Salida: 7.857
Explicación:
Una forma de obtener la máxima ganancia es:
- Tome todo el segundo bloque, obteniendo una ganancia de 5 y reduciendo la capacidad a 5.
- Tome una fracción de 5/7 del tercer bloque, obteniendo una ganancia de (5/7)*4 = 2.857 y reduciendo la capacidad a 0.
Así, el beneficio máximo obtenido es igual a (5+2.857 = 7.857), que es el máximo posible.
Entrada: A[]= {2, 5, 3}, B[] = {7, 6, 9), W = 8
Salida: 19.600
Enfoque: el problema dado se puede resolver usando un algoritmo codicioso conocido como mochila fraccionada . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de pares, digamos V , para almacenar los pares formados al tomar los elementos de la array de la array B[] como el primer elemento y los elementos de la array de la array B[] como el segundo elemento presente en el mismo índice.
- Itere sobre el rango [0, N] y si A[i] no es un cuadrado perfecto , entonces empuje el par {B[i], A[i]} en el vector V .
- Ordene el vector V en orden descendente por un comparador personalizado por las proporciones de los pares.
- Inicialice una variable, por ejemplo , la ganancia como 0 para almacenar la ganancia máxima.
- Recorra el vector V y realice los siguientes pasos en cada iteración:
- Si el segundo elemento del par actual es menor o igual que W , entonces incremente la ganancia en el primer elemento del par, es decir, tome todo el bloque de oro y luego reduzca W en el segundo elemento del par actual .
- De lo contrario, tome una cantidad igual a la relación de W y el segundo elemento del par actual y guárdelo en una variable P . Luego incremente la ganancia por P*primer elemento del par actual y luego quiebre.
- Finalmente, después de completar los pasos anteriores, imprima el valor obtenido en la ganancia como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Custom comparator
bool comp(pair<long long, long long> p1,
pair<long long, long long> p2)
{
long double a = p1.first, b = p1.second;
long double c = p2.first, d = p2.second;
long double val1 = 0, val2 = 0;
val1 = a / b;
val2 = c / d;
return val1 > val2;
}
// Function to find the maximum profit
long double maximumProfit(int A[], int B[], int N,
long long W)
{
// Stores the pairs of elements
// of B and A at the same index
vector<pair<long long, long long> > V;
// Iterate over the range
//[0, N]
for (int i = 0; i < N; i++) {
long long temp = sqrt(A[i]);
// If current integer is
// perfect square
if (temp * temp == A[i])
continue;
// Push the pair of B[i]
// and A[i] in vector V
V.push_back({ B[i], A[i] });
}
// Sorts the vector using
// the custom comparator
sort(V.begin(), V.end(), comp);
// Stores the maximum profit
long double profit = 0.00;
// Traverse the vector V
for (int i = 0; i < V.size(); i++) {
// If V[i].second is less
// than W
if (V[i].second <= W) {
// Increment profit by
// V[i].first
profit += V[i].first;
// Decrement V[i].second
// from W
W -= V[i].second;
}
// Otherwise
else {
// Update profit
profit += V[i].first
* ((long double)W / V[i].second);
break;
}
}
// Return the value of profit
return profit;
}
// Driver Code
int main()
{
int N = 3;
long long W = 10;
int A[] = { 4, 5, 7 };
int B[] = { 8, 5, 4 };
cout << maximumProfit(A, B, N, W) << endl;
return 0;
}
Python3
# Python3 program for the above approach import math from functools import cmp_to_key # Custom comparator def comparator(p1, p2): a = p1[0] b = p1[1] c = p2[0] d = p2[1] val1 = a / b val2 = c / d return val1 > val2 # Function to find the maximum profit def maximumProfit(A, B, N, W): # Stores the pairs of elements # of B and A at the same index V = [] # Iterate over the range [0,N] for i in range(0, N): temp = int(math.sqrt(A[i])) # If current integer is # perfect square if temp * temp == A[i]: continue # Push the pair of B[i] # and A[i] in vector V V.append([B[i], A[i]]) # Sort the vector using # the custom comparator V = sorted(V, key = cmp_to_key(comparator)) # Stores the maximum profit profit = 0.00 # Traverse the vector V k = len(V) for i in range(k): # If V[i][1] is less # than W if V[i][1] <= W: # Increment profit by # V[i][0] profit += V[i][0] # Decrement V[i][0] # from W W -= V[i][1] # Otherwise else: # Update profit profit += (V[i][0] * W) / V[i][1] break # Return the value of profit return profit # Driver Code if __name__ == '__main__': N = 3 W = 10 A = [ 4, 5, 7 ] B = [ 8, 5, 4 ] print(round(maximumProfit(A, B, N, W), 5)) # This code is contributed by MuskanKalra1
Javascript
<script>
// JavaScript program for the above approach
// Custom comparator
function comp(p1, p2) {
let a = p1[0], b = p1[1];
let c = p2[0], d = p2[1];
let val1 = 0, val2 = 0;
val1 = Math.floor(a / b);
val2 = Math.floor(c / d);
return val1 > val2;
}
// Function to find the maximum profit
function maximumProfit(A, B, N, W) {
// Stores the pairs of elements
// of B and A at the same index
let V = [];
// Iterate over the range
//[0, N]
for (let i = 0; i < N; i++) {
let temp = Math.sqrt(A[i]);
// If current integer is
// perfect square
if (temp * temp == A[i])
continue;
// Push the pair of B[i]
// and A[i] in vector V
V.push([B[i], A[i]]);
}
// Sorts the vector using
// the custom comparator
V.sort(comp);
// Stores the maximum profit
let profit = 0.00;
// Traverse the vector V
for (let i = 0; i < V.length; i++) {
// If V[i][1] is less
// than W
if (V[i][1] <= W) {
// Increment profit by
// V[i][0]
profit += V[i][0];
// Decrement V[i][1]
// from W
W -= V[i][1];
}
// Otherwise
else {
// Update profit
profit += V[i][0]
* (W / V[i][1]);
break;
}
}
// Return the value of profit
return profit.toFixed(5);
}
// Driver Code
let N = 3;
let W = 10;
let A = [4, 5, 7];
let B = [8, 5, 4];
document.write(maximumProfit(A, B, N, W) + "<br>");
</script>
Producción
7.85714
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)