Dadas dos arrays A[] y B[] , cada una de tamaño N , y dos enteros X e Y que indican el número máximo de elementos que se pueden seleccionar de A[] y B[] respectivamente, la tarea es encontrar el máximo posible sum seleccionando N elementos de tal manera que para cualquier índice i , se puede elegir A[i] o B[i].
Nota: Se garantiza que (X + Y) >= N.
Ejemplos:
Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}, X = 3, Y = 2 Salida: 21 i = 0
– >
5 elegido
i = 1 -> 4 elegido
i = 2 -> 3 elegido
i = 3 -> 4 elegido
i = 4 -> 5 elegido
5 + 4 + 3 + 4 + 5 = 21
Entrada: A[] = {1, 4 , 3, 2, 7, 5, 9, 6}, B[] = {1, 2, 3, 6, 5, 4, 9, 8}, X = 4, Y = 4 Salida
: 43
Enfoque codicioso: El enfoque codicioso para resolver este problema ya se ha discutido en esta publicación .
Enfoque de Programación Dinámica: En este artículo, estamos discutiendo una solución basada en Programación Dinámica .
Siga los pasos a continuación para resolver el problema:
- Los elementos máximos mínimos (N, X) se pueden seleccionar de A[] y los elementos mínimos (N, Y) se pueden seleccionar de B[] .
- Inicialice una array 2D dp[][] tal que dp[i][j] contenga la suma máxima posible seleccionando i elementos de A[] y j elementos de B[] donde i y j varían dentro de min (N, X) y min (N, X) respectivamente.
- Inicialice una variable max_sum para almacenar la suma máxima posible.
- Recorra la array y para cada array, el elemento haga lo siguiente:
- El (i + j) ésimo elemento puede ser A[i + j – 1] o B[i + j – 1] .
- Si el (i + j) ésimo elemento se selecciona de A[] , entonces el costo del (i + 1) ésimo elemento en A[] se agregará al costo total. Por lo tanto, el costo de seleccionar (i + 1) el elemento th es dp[i][j] = dp[ i – 1 ][ j ] + A[ i + j – 1 ] para este caso.
- Si el elemento (i + j) se selecciona de B[] , entonces el costo de seleccionar (i + 1) el elemento es dp[i][j] = dp[ i – 1 ][ j ] + B[ i + j – 1 ] .
- Ahora, el objetivo es maximizar el costo. Por lo tanto, la relación de recurrencia es:
dp[i][j] = max(dp[ i – 1 ][ j ] + A[ i + j – 1 ], dp[ i – 1 ][ j ] + B[ i + j – 1 ])
- Sigue actualizando max_sum después de cada iteración. Después de completar el recorrido de la array, imprima el valor final de max_sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum sum
// possible by selecting an element
// from one of two arrays for every index
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum sum
int maximumSum(int A[], int B[],
int length,
int X, int Y)
{
int l = length;
// Maximum elements that can be
// chosen from array A
int l1 = min(length, X);
// Maximum elements that can be
// chosen from array B
int l2 = min(length, Y);
int dp[l1 + 1][l2 + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 0;
// Stores the maximum
// sum possible
int max_sum = INT_MIN;
// Fill the dp[][] for base case when
// all elements are selected from A[]
for (int i = 1; i <= l1; i++) {
dp[i][0] = dp[i - 1][0] + A[i - 1];
max_sum = max(max_sum, dp[i][0]);
}
// Fill the dp[][] for base case when
// all elements are selected from B[]
for (int i = 1; i <= l2; i++) {
dp[0][i] = dp[0][i - 1] + B[i - 1];
max_sum = max(max_sum, dp[0][i]);
}
for (int i = 1; i <= l1; i++) {
for (int j = 1; j <= l2; j++) {
if (i + j <= l)
dp[i][j]
= max(dp[i - 1][j]
+ A[i + j - 1],
dp[i][j - 1]
+ B[i + j - 1]);
max_sum = max(dp[i][j],
max_sum);
}
}
// Return the final answer
return max_sum;
}
// Driver Program
int main()
{
int A[] = { 1, 2, 3, 4, 5 };
int B[] = { 5, 4, 3, 2, 1 };
int X = 3, Y = 2;
int N = sizeof(A) / sizeof(A[0]);
cout << maximumSum(A, B, N, X, Y);
return 0;
}
Java
// Java program to find maximum sum
// possible by selecting an element
// from one of two arrays for every index
class GFG{
// Function to calculate maximum sum
static int maximumSum(int A[], int B[],
int length, int X,
int Y)
{
int l = length;
// Maximum elements that can be
// chosen from array A
int l1 = Math.min(length, X);
// Maximum elements that can be
// chosen from array B
int l2 = Math.min(length, Y);
int dp[][] = new int [l1 + 1][l2 + 1];
// Stores the maximum
// sum possible
int max_sum = Integer.MIN_VALUE;
// Fill the dp[][] for base case when
// all elements are selected from A[]
for(int i = 1; i <= l1; i++)
{
dp[i][0] = dp[i - 1][0] + A[i - 1];
max_sum = Math.max(max_sum, dp[i][0]);
}
// Fill the dp[][] for base case when
// all elements are selected from B[]
for(int i = 1; i <= l2; i++)
{
dp[0][i] = dp[0][i - 1] + B[i - 1];
max_sum = Math.max(max_sum, dp[0][i]);
}
for(int i = 1; i <= l1; i++)
{
for(int j = 1; j <= l2; j++)
{
if (i + j <= l)
dp[i][j] = Math.max(dp[i - 1][j] +
A[i + j - 1],
dp[i][j - 1] +
B[i + j - 1]);
max_sum = Math.max(dp[i][j], max_sum);
}
}
// Return the final answer
return max_sum;
}
// Driver code
public static void main (String[] args)
{
int A[] = new int[]{ 1, 2, 3, 4, 5 };
int B[] = new int[]{ 5, 4, 3, 2, 1 };
int X = 3, Y = 2;
int N = A.length;
System.out.println(maximumSum(A, B, N, X, Y));
}
}
// This code is contributed by Pratima Pandey
Python
# Python3 program to find maximum sum # possible by selecting an element # from one of two arrays for every index # Function to calculate maximum sum def maximumSum(A, B, length, X, Y): l = length # Maximum elements that can be # chosen from array A l1 = min(length, X) # Maximum elements that can be # chosen from array B l2 = min(length, Y) dp=[[ 0 for i in range(l2 + 1)] for i in range(l1 + 1)] dp[0][0] = 0 # Stores the maximum # sum possible max_sum = -10 * 9 # Fill the dp[]for base case when # all elements are selected from A[] for i in range(1, l1 + 1): dp[i][0] = dp[i - 1][0] + A[i - 1] max_sum = max(max_sum, dp[i][0]) # Fill the dp[]for base case when # all elements are selected from B[] for i in range(1, l2 + 1): dp[0][i] = dp[0][i - 1] + B[i - 1] max_sum = max(max_sum, dp[0][i]) for i in range(1, l1 + 1): for j in range(1, l2 + 1): if (i + j <= l): dp[i][j]= max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]) max_sum = max(dp[i][j], max_sum) # Return the final answer return max_sum # Driver Program if __name__ == '__main__': A= [1, 2, 3, 4, 5] B= [5, 4, 3, 2, 1] X = 3 Y = 2 N = len(A) print(maximumSum(A, B, N, X, Y)) # This code is contributed by Mohit Kumar 29
C#
// C# program to find maximum sum
// possible by selecting an element
// from one of two arrays for every index
using System;
class GFG{
// Function to calculate maximum sum
static int maximumSum(int []A, int []B,
int length, int X,
int Y)
{
int l = length;
// Maximum elements that can be
// chosen from array A
int l1 = Math.Min(length, X);
// Maximum elements that can be
// chosen from array B
int l2 = Math.Min(length, Y);
int [,]dp = new int [l1 + 1, l2 + 1];
// Stores the maximum
// sum possible
int max_sum = int.MinValue;
// Fill the [,]dp for base case when
// all elements are selected from []A
for(int i = 1; i <= l1; i++)
{
dp[i, 0] = dp[i - 1, 0] + A[i - 1];
max_sum = Math.Max(max_sum, dp[i, 0]);
}
// Fill the [,]dp for base case when
// all elements are selected from []B
for(int i = 1; i <= l2; i++)
{
dp[0, i] = dp[0, i - 1] + B[i - 1];
max_sum = Math.Max(max_sum, dp[0, i]);
}
for(int i = 1; i <= l1; i++)
{
for(int j = 1; j <= l2; j++)
{
if (i + j <= l)
dp[i, j] = Math.Max(dp[i - 1, j] +
A[i + j - 1],
dp[i, j - 1] +
B[i + j - 1]);
max_sum = Math.Max(dp[i, j], max_sum);
}
}
// Return the readonly answer
return max_sum;
}
// Driver code
public static void Main(String[] args)
{
int []A = new int[]{ 1, 2, 3, 4, 5 };
int []B = new int[]{ 5, 4, 3, 2, 1 };
int X = 3, Y = 2;
int N = A.Length;
Console.WriteLine(maximumSum(A, B, N, X, Y));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to find maximum sum
// possible by selecting an element
// from one of two arrays for every index
// Function to calculate maximum sum
function maximumSum(A, B, length, X, Y)
{
var l = length;
// Maximum elements that can be
// chosen from array A
var l1 = Math.min(length, X);
// Maximum elements that can be
// chosen from array B
var l2 = Math.min(length, Y);
var dp = Array.from(Array(l1+1),
()=> Array(l2+1).fill(0));
dp[0][0] = 0;
// Stores the maximum
// sum possible
var max_sum = -1000000000;
// Fill the dp[][] for base case when
// all elements are selected from A[]
for (var i = 1; i <= l1; i++) {
dp[i][0] = dp[i - 1][0] + A[i - 1];
max_sum = Math.max(max_sum, dp[i][0]);
}
// Fill the dp[][] for base case when
// all elements are selected from B[]
for (var i = 1; i <= l2; i++) {
dp[0][i] = dp[0][i - 1] + B[i - 1];
max_sum = Math.max(max_sum, dp[0][i]);
}
for (var i = 1; i <= l1; i++) {
for (var j = 1; j <= l2; j++) {
if (i + j <= l)
dp[i][j]
= Math.max(dp[i - 1][j]
+ A[i + j - 1],
dp[i][j - 1]
+ B[i + j - 1]);
max_sum = Math.max(dp[i][j],
max_sum);
}
}
// Return the final answer
return max_sum;
}
// Driver Program
var A = [ 1, 2, 3, 4, 5 ];
var B = [ 5, 4, 3, 2, 1 ];
var X = 3, Y = 2;
var N = A.length;
document.write( maximumSum(A, B, N, X, Y));
</script>
Producción:
21
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por animesh_ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA