Dadas tres arrays A[] , B[] y C[] de tamaño N y tres enteros positivos X , Y y Z , la tarea es encontrar la suma máxima posible seleccionando como máximo N elementos de la array de manera que como máximo X elementos son de la array A[] , como máximo Y elementos de la array B[] , como máximo Z elementos son de la array C[] y todos los elementos son de diferentes índices.
Ejemplos:
Entrada: A[] = {10, 0, 5}, B[] = {5, 10, 0}, C[] = {0, 5, 10}, X = 1, Y = 1, Z = 1
Salida : 30
Explicación:
Seleccionar A[0], B[1], C[2] hace que la suma = A[0] + B[1] + C[2] = 30, que es la suma máxima posible después de satisfacer el condiciones.
Por lo tanto, la salida requerida es 30.Entrada: A[] = {0}, B[] = {0}, C[] = {0}, X = 1, Y = 1, Z = 1
Salida: 0
Enfoque ingenuo: siga los pasos a continuación para resolver el problema:
- Recorra todas las arrays y genere todas las combinaciones posibles para seleccionar como máximo N elementos de las tres arrays diferentes que satisfagan la condición dada:
- Para cada i -ésimo elemento, se pueden realizar las siguientes cuatro operaciones:
- Seleccione el i -ésimo elemento de la array, A[] .
- Seleccione el i -ésimo elemento de la array, A[] .
- Seleccione el i -ésimo elemento de la array, A[] .
- Seleccione i -ésimo elemento de cualquiera de las arrays.
- Por lo tanto, la relación de recurrencia para resolver el problema es la siguiente:
FindMaxS(X, Y, Z, i) = max(A[i] + FindMaxS(X – 1, Y, Z, i – 1), B[i] + FindMaxS(X, Y – 1, Z, i – 1), C[i] + FindMaxS(X, Y, Z – 1, i – 1), FindMaxS(X, Y, Z, i – 1))
- Usando la relación de recurrencia anterior, imprima la suma máxima de seleccionar N elementos de array en función de las condiciones dadas.
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 to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
int FindMaxS(int X, int Y, int Z, int n, vector<int>& A,
vector<int>& B, vector<int>& C)
{
// Base Cases
if (X < 0 or Y < 0 or Z < 0)
return INT_MIN;
if (n < 0)
return 0;
// Selecting i-th element from A[]
int ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from B[]
int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1,
A, B, C);
// Selecting i-th element from C[]
int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
int no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
int maximum = max(ch, max(ca, max(co, no)));
return maximum;
}
// Driver Code
int main()
{
// Given X, Y and Z
int X = 1;
int Y = 1;
int Z = 1;
// Given A[]
vector<int> A = { 10, 0, 5 };
// Given B[]
vector<int> B = { 5, 10, 0 };
// Given C[]
vector<int> C = { 0, 5, 10 };
// Given Size
int n = B.size();
// Function Call
cout << FindMaxS(X, Y, Z, n - 1, A, B, C);
}
Java
// Java program for the above approach
class GFG{
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
static int FindMaxS(int X, int Y, int Z, int n,
int A[], int B[], int C[])
{
// Base Cases
if (X < 0 || Y < 0 || Z < 0)
return Integer.MIN_VALUE;
if (n < 0)
return 0;
// Selecting i-th element from A[]
int ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from B[]
int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1,
A, B, C);
// Selecting i-th element from C[]
int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
int no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
int maximum = Math.max(ch, Math.max(
ca, Math.max(co, no)));
return maximum;
}
// Driver Code
public static void main (String[] args)
{
// Given X, Y and Z
int X = 1;
int Y = 1;
int Z = 1;
// Given A[]
int A[] = { 10, 0, 5 };
// Given B[]
int B[] = { 5, 10, 0 };
// Given C[]
int C[] = { 0, 5, 10 };
// Given Size
int n = B.length;
// Function Call
System.out.println(FindMaxS(X, Y, Z, n - 1, A, B, C));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find maximum sum of at most N with # different index array elements such that at most X # are from A[], Y are from B[] and Z are from C[] def FindMaxS(X, Y, Z, n): global A, B, C if (X < 0 or Y < 0 or Z < 0): return -10**9 if (n < 0): return 0 # Selecting i-th element from A[] ch = A[n] + FindMaxS(X - 1, Y, Z,n - 1) # Selecting i-th element from B[] ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1) # Selecting i-th element from C[] co = C[n] + FindMaxS(X, Y, Z - 1, n - 1) # i-th elements not selected from # any of the arrays no = FindMaxS(X, Y, Z, n - 1) # Select the maximum sum from all # the possible calls maximum = max(ch, max(ca, max(co, no))) return maximum # Driver Code if __name__ == '__main__': # Given X, Y and Z X = 1 Y = 1 Z = 1 # Given A[] A = [10, 0, 5] # Given B[] B = [5, 10, 0] # Given C[] C = [0, 5, 10] # Given Size n = len(B) # Function Call print (FindMaxS(X, Y, Z, n - 1)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from []A, Y are from []B and Z are from C[]
static int FindMaxS(int X, int Y, int Z, int n,
int []A, int []B, int []C)
{
// Base Cases
if (X < 0 || Y < 0 || Z < 0)
return int.MinValue;
if (n < 0)
return 0;
// Selecting i-th element from []A
int ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from []B
int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1,
A, B, C);
// Selecting i-th element from C[]
int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
int no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
int maximum = Math.Max(ch, Math.Max(
ca, Math.Max(co, no)));
return maximum;
}
// Driver Code
public static void Main(String[] args)
{
// Given X, Y and Z
int X = 1;
int Y = 1;
int Z = 1;
// Given []A
int []A = { 10, 0, 5 };
// Given []B
int []B = { 5, 10, 0 };
// Given C[]
int []C = { 0, 5, 10 };
// Given Size
int n = B.Length;
// Function Call
Console.WriteLine(FindMaxS(X, Y, Z, n - 1, A, B, C));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
function FindMaxS(X, Y, Z, n, A, B, C)
{
// Base Cases
if (X < 0 || Y < 0 || Z < 0)
return -1000000000;
if (n < 0)
return 0;
// Selecting i-th element from A[]
var ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from B[]
var ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1,
A, B, C);
// Selecting i-th element from C[]
var co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
var no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
var maximum = Math.max(ch, Math.max(ca, Math.max(co, no)));
return maximum;
}
// Driver Code
// Given X, Y and Z
var X = 1;
var Y = 1;
var Z = 1;
// Given A[]
var A = [10, 0, 5];
// Given B[]
var B = [5, 10, 0];
// Given C[]
var C = [0, 5, 10];
// Given Size
var n = B.length;
// Function Call
document.write( FindMaxS(X, Y, Z, n - 1, A, B, C));
</script>
Producción:
30
Complejidad temporal: O(4 N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la memorización . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 4D, digamos dp[N][X][Y][Z] , para almacenar los subproblemas superpuestos de la relación de recurrencia anterior.
- Use la relación de recurrencia anterior e imprima el valor de dp[N][X][Y][Z] usando memoization .
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;
// Store overlapping subproblems
// of the recurrence relation
int dp[50][50][50][50];
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
int FindMaxS(int X, int Y, int Z, int n, vector<int>& A,
vector<int>& B, vector<int>& C)
{
// Base Cases
if (X < 0 or Y < 0 or Z < 0)
return INT_MIN;
if (n < 0)
return 0;
// If the subproblem already computed
if (dp[n][X][Y][Z] != -1) {
return dp[n][X][Y][Z];
}
// Selecting i-th element from A[]
int ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from B[]
int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1,
A, B, C);
// Selecting i-th element from C[]
int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
int no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
int maximum = max(ch, max(ca, max(co, no)));
return dp[n][X][Y][Z] = maximum;
}
// Driver Code
int main()
{
// Given X, Y and Z
int X = 1;
int Y = 1;
int Z = 1;
// Given A[]
vector<int> A = { 10, 0, 5 };
// Given B[]
vector<int> B = { 5, 10, 0 };
// Given C[]
vector<int> C = { 0, 5, 10 };
// Given Size
int n = B.size();
memset(dp, -1, sizeof(dp));
// Function Call
cout << FindMaxS(X, Y, Z, n - 1, A, B, C);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Store overlapping subproblems
// of the recurrence relation
static int [][][][]dp = new int[50][50][50][50];
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
static int FindMaxS(int X, int Y, int Z, int n,
int []A, int []B, int []C)
{
// Base Cases
if (X < 0 || Y < 0 || Z < 0)
return Integer.MIN_VALUE;
if (n < 0)
return 0;
// If the subproblem already computed
if (dp[n][X][Y][Z] != -1)
{
return dp[n][X][Y][Z];
}
// Selecting i-th element from A[]
int ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from B[]
int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1,
A, B, C);
// Selecting i-th element from C[]
int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
int no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
int maximum = Math.max(
ch, Math.max(ca, Math.max(co, no)));
return dp[n][X][Y][Z] = maximum;
}
// Driver Code
public static void main(String[] args)
{
// Given X, Y and Z
int X = 1;
int Y = 1;
int Z = 1;
// Given A[]
int []A = { 10, 0, 5 };
// Given B[]
int []B = { 5, 10, 0 };
// Given C[]
int []C = { 0, 5, 10 };
// Given Size
int n = B.length;
for(int i = 0; i < 50; i++)
for(int j = 0; j < 50; j++)
for(int k = 0; k < 50; k++)
for(int l = 0; l < 50; l++)
dp[i][j][k][l] = -1;
// Function Call
System.out.print(FindMaxS(X, Y, Z, n - 1,
A, B, C));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach import sys # Store overlapping subproblems # of the recurrence relation dp = [[[[-1 for i in range(50)] for j in range(50)] for k in range(50)] for l in range(50)] # Function to find maximum sum of at most N with # different index array elements such that at most X # are from A[], Y are from B[] and Z are from C[] def FindMaxS(X, Y, Z, n, A, B, C): # Base Cases if (X < 0 or Y < 0 or Z < 0): return -sys.maxsize - 1 if (n < 0): return 0 # If the subproblem already computed if (dp[n][X][Y][Z] != -1): return dp[n][X][Y][Z] # Selecting i-th element from A[] ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C) # Selecting i-th element from B[] ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C) # Selecting i-th element from C[] co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,A, B, C) # i-th elements not selected from # any of the arrays no = FindMaxS(X, Y, Z, n - 1, A, B, C) # Select the maximum sum from all # the possible calls maximum = max(ch, max(ca, max(co, no))) dp[n][X][Y][Z] = maximum return dp[n][X][Y][Z] # Driver Code if __name__ == '__main__': # Given X, Y and Z X = 1 Y = 1 Z = 1 # Given A[] A = [10, 0, 5] # Given B[] B = [5, 10, 0] # Given C[] C = [0, 5, 10] # Given Size n = len(B) # Function Call print(FindMaxS(X, Y, Z, n - 1, A, B, C)) # This code is contributed by bgangwar59
C#
// C# program for the above approach
using System;
class GFG{
// Store overlapping subproblems
// of the recurrence relation
static int[,,,] dp = new int[50, 50, 50, 50];
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
static int FindMaxS(int X, int Y, int Z, int n,
int[] A, int[] B, int[] C)
{
// Base Cases
if (X < 0 || Y < 0 || Z < 0)
return Int32.MinValue;
if (n < 0)
return 0;
// If the subproblem already computed
if (dp[n, X, Y, Z] != -1)
{
return dp[n, X, Y, Z];
}
// Selecting i-th element from A[]
int ch = A[n] + FindMaxS(X - 1, Y, Z,
n - 1, A, B, C);
// Selecting i-th element from B[]
int ca = B[n] + FindMaxS(X, Y - 1, Z,
n - 1, A, B, C);
// Selecting i-th element from C[]
int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1,
A, B, C);
// i-th elements not selected from
// any of the arrays
int no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
int maximum = Math.Max(
ch, Math.Max(ca, Math.Max(co, no)));
return dp[n, X, Y, Z] = maximum;
}
// Driver Code
public static void Main(string[] args)
{
// Given X, Y and Z
int X = 1;
int Y = 1;
int Z = 1;
// Given A[]
int[] A = { 10, 0, 5 };
// Given B[]
int[] B = { 5, 10, 0 };
// Given C[]
int[] C = { 0, 5, 10 };
// Given Size
int n = B.Length;
for(int i = 0; i < 50; i++)
for(int j = 0; j < 50; j++)
for(int k = 0; k < 50; k++)
for(int l = 0; l < 50; l++)
dp[i, j, k, l] = -1;
// Function Call
Console.Write(FindMaxS(X, Y, Z, n - 1, A, B, C));
}
}
// This code is contributed by chitranayal
Javascript
<script>
// JavaScript program for the above approach
// Store overlapping subproblems
// of the recurrence relation
let dp = new Array(50);
// Function to find maximum sum of at most N with
// different index array elements such that at most X
// are from A[], Y are from B[] and Z are from C[]
function FindMaxS(X, Y, Z, n, A, B, C)
{
// Base Cases
if (X < 0 || Y < 0 || Z < 0)
return Number.MIN_VALUE;
if (n < 0)
return 0;
// If the subproblem already computed
if (dp[n][X][Y][Z] != -1)
{
return dp[n][X][Y][Z];
}
// Selecting i-th element from A[]
let ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C);
// Selecting i-th element from B[]
let ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C);
// Selecting i-th element from C[]
let co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C);
// i-th elements not selected from
// any of the arrays
let no = FindMaxS(X, Y, Z, n - 1, A, B, C);
// Select the maximum sum from all
// the possible calls
let maximum = Math.max(ch, Math.max(ca, Math.max(co, no)));
dp[n][X][Y][Z] = maximum;
return dp[n][X][Y][Z];
}
// Given X, Y and Z
let X = 1;
let Y = 1;
let Z = 1;
// Given A[]
let A = [ 10, 0, 5 ];
// Given B[]
let B = [ 5, 10, 0 ];
// Given C[]
let C = [ 0, 5, 10 ];
// Given Size
let n = B.length;
for(let i = 0; i < 50; i++)
{
dp[i] = new Array(50);
for(let j = 0; j < 50; j++)
{
dp[i][j] = new Array(50);
for(let k = 0; k < 50; k++)
{
dp[i][j][k] = new Array(50);
for(let l = 0; l < 50; l++)
{
dp[i][j][k][l] = -1;
}
}
}
}
// Function Call
document.write(FindMaxS(X, Y, Z, n - 1, A, B, C));
</script>
Producción:
30
Complejidad de tiempo : O (N * X * Y * Z)
Complejidad espacial: O(N * X * Y * Z)
Publicación traducida automáticamente
Artículo escrito por yashshah14093 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA