Rahul y Ankit son los dos únicos camareros del Royal Restaurant. Hoy, el restaurante recibió N pedidos. La cantidad de propinas puede diferir cuando las manejan diferentes camareros y se dan como arrays A[] y B[] , de modo que si Rahul toma la i -ésima orden, recibirá una propina de A[i] rupias, y si Ankit toma esta orden, el La propina sería B[i] rupias.
Para maximizar el valor total de la propina, decidieron distribuir el pedido entre ellos. Un pedido será manejado por una sola persona . Además, debido a limitaciones de tiempo , Rahul no puede aceptar más de X pedidos y Ankit no puede aceptar más de Y pedidos. Se garantiza que X + Y es mayor o igual que N , lo que significa que todos los pedidos pueden ser manejados por Rahul o Ankit. La tarea es averiguar la cantidad máxima posible de dinero total de propinas después de procesar todos los pedidos.
Ejemplos:
Entrada: N = 5, X = 3, Y = 3, A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}
Salida: 21
Explicación:
Paso 1: 5 está incluido en la array de Ankit
Paso 2: 4 está incluido en la array de Ankit
Paso 3: Como ambos tienen el mismo valor 3, elija cualquiera de ellos
Paso 4: 4 está incluido en la array de Rahul
Paso 4: 5 está incluido de la array de Rahul
Por lo tanto, la cantidad máxima posible de dinero total de propinas suma 21.Entrada: N = 7, X = 3, Y = 4, A[] = {8, 7, 15, 19, 16, 16, 18}, B[] = {1, 7, 15, 11, 12, 31 , 9}
Salida: 110
Enfoque ingenuo: el enfoque más simple es atravesar las arrays dadas y comenzar a atravesar ambas arrays simultáneamente y elegir el elemento máximo entre ellos y reducir el recuento de X si el elemento se toma de X , de lo contrario, el recuento de Y. Si uno de los X o Y se convierte en 0 , atraviesa otra array distinta de cero y agrega su valor a la ganancia máxima. Como en cada paso, hay una elección que hacer, esto es similar al problema de la mochila 0-1 , en el que se toman decisiones sobre si incluir o excluir un elemento.
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;
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
int maximumTip(vector<int> &arr1,vector<int> & arr2,
int n, int x, int y)
{
// Base Condition
if (n == 0)
return 0;
// If both have non-zero count then
// return max element from both array
if (x != 0 and y != 0)
return max(
arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y),
arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
y - 1));
// Traverse first array, as y
// count has become 0
if (y == 0)
return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y);
// Traverse 2nd array, as x
// count has become 0
else
return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
x, y - 1);
}
// Drive Code
int main()
{
int N = 5;
int X = 3;
int Y = 3;
vector<int> A = { 1, 2, 3, 4, 5 };
vector<int> B = { 5, 4, 3, 2, 1 };
// Function Call
cout << (maximumTip(A, B, N, X, Y));
}
// This code is contributed by mohit kumar 29
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
static int maximumTip(int []arr1,int []arr2,
int n, int x, int y)
{
// Base Condition
if (n == 0)
return 0;
// If both have non-zero count then
// return max element from both array
if (x != 0 && y != 0)
return Math.max(
arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y),
arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
y - 1));
// Traverse first array, as y
// count has become 0
if (y == 0)
return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y);
// Traverse 2nd array, as x
// count has become 0
else
return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
x, y - 1);
}
// Drive Code
public static void main (String[] args) {
int N = 5;
int X = 3;
int Y = 3;
int A[] = { 1, 2, 3, 4, 5 };
int B[] = { 5, 4, 3, 2, 1 };
// Function Call
System.out.println(maximumTip(A, B, N, X, Y));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python program for the above approach # Function that finds the maximum tips # from the given arrays as per the # given conditions def maximumTip(arr1, arr2, n, x, y): # Base Condition if n == 0: return 0 # If both have non-zero count then # return max element from both array if x != 0 and y != 0: return max( arr1[n-1] + maximumTip(arr1, arr2, n - 1, x-1, y), arr2[n-1] + maximumTip(arr1, arr2, n-1, x, y-1) ) # Traverse first array, as y # count has become 0 if y == 0: return arr1[n-1] + maximumTip(arr1, arr2, n-1, x-1, y) # Traverse 2nd array, as x # count has become 0 else: return arr2[n - 1] + maximumTip(arr1, arr2, n-1, x, y-1) # Drive Code N = 5 X = 3 Y = 3 A = [1, 2, 3, 4, 5] B = [5, 4, 3, 2, 1] # Function Call print(maximumTip(A, B, N, X, Y))
C#
/*package whatever //do not write package name here */
using System;
public class GFG
{
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
static int maximumTip(int []arr1,int []arr2,
int n, int x, int y)
{
// Base Condition
if (n == 0)
return 0;
// If both have non-zero count then
// return max element from both array
if (x != 0 && y != 0)
return Math.Max(
arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y),
arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
y - 1));
// Traverse first array, as y
// count has become 0
if (y == 0)
return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y);
// Traverse 2nd array, as x
// count has become 0
else
return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
x, y - 1);
}
// Drive Code
public static void Main(String[] args) {
int N = 5;
int X = 3;
int Y = 3;
int []A = { 1, 2, 3, 4, 5 };
int []B = { 5, 4, 3, 2, 1 };
// Function Call
Console.WriteLine(maximumTip(A, B, N, X, Y));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript Program for the above approach
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
function maximumTip(arr1, arr2, n, x, y) {
// Base Condition
if (n == 0)
return 0;
// If both have non-zero count then
// return max element from both array
if (x != 0 && y != 0)
return Math.max(
arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y),
arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x,
y - 1));
// Traverse first array, as y
// count has become 0
if (y == 0)
return arr1[n - 1] + maximumTip(arr1, arr2, n - 1,
x - 1, y);
// Traverse 2nd array, as x
// count has become 0
else
return arr2[n - 1] + maximumTip(arr1, arr2, n - 1,
x, y - 1);
}
// Drive Code
let N = 5;
let X = 3;
let Y = 3;
let A = [1, 2, 3, 4, 5];
let B = [5, 4, 3, 2, 1];
// Function Call
document.write(maximumTip(A, B, N, X, Y));
// This code is contributed by Potta Lokesh
</script>
21
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de programación dinámica y memorización . Si se rastrea la ejecución para los valores de N , X , Y , se puede ver que hay subproblemas superpuestos . Estos subproblemas superpuestos se pueden calcular una vez y almacenar y utilizar cuando se llama al mismo subproblema en la llamada recursiva . A continuación se muestran los pasos:
- Inicialice un Mapa/Diccionario para almacenar el resultado de los subproblemas superpuestos. Las claves del mapa serán valores combinados de N , X e Y .
- En cada llamada recursiva, verifique si una clave determinada está presente en el mapa y luego devuelva el valor del mapa mismo.
- De lo contrario, llame a la función de forma recursiva y almacene el valor en el mapa y devuelva el valor almacenado.
- Si X e Y son distintos de cero, llame recursivamente a la función y tome el máximo del valor devuelto cuando se usa X y cuando se usa Y.
- Si X o Y es cero, llame recursivamente a la array distinta de cero.
- Después de que finalicen las llamadas recursivas anteriores, imprima la cantidad máxima posible de propina calculada.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int dp[1001][101][101];
int rec(int level, int x, int y, int arr1[], int arr2[],
int n)
{
if (level == n)
return 0;
if (x == 0 && y == 0)
return 0;
if (x == 0)
return arr2[level]
+ rec(level + 1, x, y - 1, arr1, arr2, n);
if (y == 0)
return arr1[level]
+ rec(level + 1, x - 1, y, arr1, arr2, n);
if (dp[level][x][y] != -1)
return dp[level][x][y];
int ans = max(rec(level + 1, x - 1, y, arr1, arr2, n)
+ arr1[level],
rec(level + 1, x, y - 1, arr1, arr2, n)
+ arr2[level]);
return dp[level][x][y] = ans;
}
void solve()
{
int n = 7, x = 3, y = 4;
int arr1[] = { 8, 7, 15, 19, 16, 16, 18 },
arr2[] = { 1, 7, 15, 11, 12, 31, 9 };
memset(dp, -1, sizeof(dp));
cout << rec(0, x, y, arr1, arr2, n);
}
int main()
{
solve();
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.HashMap;
class GFG {
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
static int maximumTip(int[] arr1, int[] arr2, int n,
int x, int y,
HashMap<String, Integer> dd)
{
// Create key of N, X, Y
String key = Integer.toString(n) + "_"
+ Integer.toString(x) + "_"
+ Integer.toString(y);
// Return if the current state is
// already calculated
if (dd.get(key) != null)
return dd.get(key);
// Base Condition
if (n == 0)
return 0;
// If both have non-zero count then store and
// return max element from both array
if (x != 0 && y != 0) {
int temp = Math.max(
arr1[n - 1]
+ maximumTip(arr1, arr2, n - 1, x - 1,
y, dd),
arr2[n - 1]
+ maximumTip(arr1, arr2, n - 1, x,
y - 1, dd));
dd.put(key, temp);
// Return the current state result
return dd.get(key);
}
// if y is zero, only x value
// can be used
if (y == 0) {
int temp = arr1[n - 1]
+ maximumTip(arr1, arr2, n - 1,
x - 1, y, dd);
dd.put(key, temp);
// Return the current state result
return dd.get(key);
}
// if x is zero, only y value
// can be used
else {
int temp = arr2[n - 1]
+ maximumTip(arr1, arr2, n - 1, x,
y - 1, dd);
dd.put(key, temp);
// Return the current state result
return dd.get(key);
}
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int X = 3;
int Y = 3;
int A[] = { 1, 2, 3, 4, 5 };
int B[] = { 5, 4, 3, 2, 1 };
// Stores the results of the
// overlapping state
HashMap<String, Integer> dd
= new HashMap<String, Integer>();
// Function Call
System.out.println(maximumTip(A, B, N, X, Y, dd));
}
}
// This code is contributed by MuskanKalra1
Python3
# Python program for the above approach
# Function that finds the maximum tips
# from the given arrays as per the
# given conditions
def maximumTip(arr1, arr2, n, x, y, dd):
# Create key of N, X, Y
key = str(n) + '_' + str(x) + '_' + str(y)
# Return if the current state is
# already calculated
if key in dd:
return dd[key]
# Base Condition
if n == 0:
return 0
# Store and return
if x != 0 and y != 0:
dd[key] = max(
arr1[n-1] + maximumTip(arr1, arr2, n-1, x-1, y, dd),
arr2[n-1] + maximumTip(arr1, arr2, n-1, x, y-1, dd)
)
# Return the current state result
return dd[key]
# If y is zero, only x value
# can be used
if y == 0:
dd[key] = arr1[n-1] + maximumTip(arr1, arr2, n-1, x-1, y, dd)
# Return the current state result
return dd[key]
# If x is zero, only y value
# can be used
else:
dd[key] = arr2[n-1] + maximumTip(arr1, arr2, n-1, x, y-1, dd)
# Return the current state result
return dd[key]
# Drive Code
N = 5
X = 3
Y = 3
A = [1, 2, 3, 4, 5]
B = [5, 4, 3, 2, 1]
# Stores the results of the
# overlapping state
dd = {}
# Function Call
print(maximumTip(A, B, N, X, Y, dd))
Javascript
<script>
// JavaScript program for the above approach
// Function that finds the maximum tips
// from the given arrays as per the
// given conditions
function maximumTip(arr1, arr2, n, x, y, dd) {
// Create key of N, X, Y
key = `${n}_${x}_${y}`;
// Return if the current state is
// already calculated
for (var key in dd) {
return dd[key];
}
// Base Condition
if (n == 0) {
return 0;
}
// Store and return
if (x != 0 && y != 0) {
dd[key] = Math.max(
arr1[n - 1] + maximumTip(arr1, arr2, n - 1, x - 1, y, dd),
arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x, y - 1, dd)
);
// Return the current state result
return dd[key];
}
// If y is zero, only x value
// can be used
if (y == 0)
{
dd[key] = arr1[n - 1] + maximumTip(arr1, arr2, n - 1, x - 1, y, dd);
// Return the current state result
return dd[key];
}
// If x is zero, only y value
// can be used
else {
dd[key] = arr2[n - 1] + maximumTip(arr1, arr2, n - 1, x, y - 1, dd);
// Return the current state result
return dd[key];
}
}
// Drive Code
let N = 5;
let X = 3;
let Y = 3;
let A = [1, 2, 3, 4, 5];
let B = [5, 4, 3, 2, 1];
// Stores the results of the
// overlapping state
dd = {};
// Function Call
document.write(maximumTip(A, B, N, X, Y, dd));
// This code is contributed by rdtank.
</script>
21
Complejidad de Tiempo: O(N*X*Y)
Espacio Auxiliar: O(N*X*Y)