Dadas tres arrays A, B y C , cada una de las cuales tiene N elementos, la tarea es encontrar la suma máxima que se puede obtener a lo largo de cualquier ruta válida con, como máximo , K saltos.
Una ruta es válida si sigue las siguientes propiedades:
- Comienza desde el índice 0 de una array.
- Termina en el índice (N-1) de una array.
- Para cualquier elemento en la ruta en el índice i, el siguiente elemento debe estar en el índice i+1 de la array actual o adyacente únicamente.
- Si la ruta implica seleccionar el siguiente elemento (i + 1) de la array adyacente, en lugar del actual, se dice que es 1 salto
Ejemplos:
Entrada: A[] = {4, 5, 1, 2, 10}, B[] = {9, 7, 3, 20, 16}, C[] = {6, 12, 13, 9, 8}, K = 2
Salida: 70
Explicación:
Partiendo de la array B y seleccionando los elementos de la siguiente manera:
Seleccione B[0]: 9 => sum = 9
Saltar a C[1]: 12 => sum = 21
Seleccione C[2]: 13 => suma = 34
Saltar a B[3]: 20 => suma = 54
Seleccionar B[4]: 16 => suma = 70
Por lo tanto suma máxima con 2 saltos como máximo = 70
Entrada: A[] = {10, 4, 1, 8}, B[] = {9, 0, 2, 5}, C[] = {6, 2, 7, 3}, K = 2
Salida: 24
Enfoque codicioso intuitivo (no correcto): una posible idea para resolver el problema podría ser elegir el elemento máximo en el índice actual y pasar al siguiente índice que tenga el valor máximo, ya sea de la array actual o de la array adyacente si quedan saltos.
Por ejemplo:
Given,
A[] = {4, 5, 1, 2, 10},
B[] = {9, 7, 3, 20, 16},
C[] = {6, 12, 13, 9, 8},
K = 2
Encontrar la solución usando el enfoque Greedy:
Current maximum: 9, K = 2, sum = 9 Next maximum: 12, K = 1, sum = 12 Next maximum: 13, K = 1, sum = 25 Next maximum: 20, K = 0, sum = 45 Adding rest of elements: 16, K = 0, sum = 61 Clearly, this is not the maximum sum.
Por lo tanto, este enfoque es incorrecto.
Enfoque de programación dinámica : el DP se puede utilizar en dos pasos: recursividad y memorización.
- Recursividad: El problema podría descomponerse usando la siguiente relación recursiva:
- En la array A, índice i con saltos K
rutaSuma(A, i, k) = A[i] + max(rutaSuma(A, i+1, k), rutaSuma(B, i+1, k-1));
- Del mismo modo, en la array B,
rutaSuma(B, i, k) = B[i] + max(rutaSuma(B, i+1, k), max(rutaSuma(A, i+1, k-1), rutaSuma(C, i+1, k-1));
- De manera similar, en la array C,
rutaSuma(C, i, k) = C[i] + max(rutaSuma(C, i+1, k), rutaSuma(B, i+1, k-1));
- Por lo tanto, la suma máxima se puede encontrar como:
maxSum = max(pathSum(A, i, k), max(pathSum(B, i, k), pathSum(C, i, k)));
- Memoización: la complejidad de la solución recursiva anterior se puede reducir con la ayuda de la memorización.
- Almacene los resultados después de calcular en una array tridimensional (dp) de tamaño [3][N][K].
- El valor de cualquier elemento de la array dp almacena la suma máxima en el i-ésimo índice con x saltos restantes en una array
A continuación se muestra la implementación del enfoque:
C++
// C++ program to maximum path sum in
// the given arrays with at most K jumps
#include <iostream>
using namespace std;
#define M 3
#define N 5
#define K 2
int dp[M][N][K];
void initializeDp()
{
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < K; k++)
dp[i][j][k] = -1;
}
// Function to calculate maximum path sum
int pathSum(int* a, int* b, int* c,
int i, int n,
int k, int on)
{
// Base Case
if (i == n)
return 0;
if (dp[on][i][k] != -1)
return dp[on][i][k];
int current, sum;
switch (on) {
case 0:
current = a[i];
break;
case 1:
current = b[i];
break;
case 2:
current = c[i];
break;
}
// No jumps available.
// Hence pathSum can be
// from current array only
if (k == 0) {
return dp[on][i][k]
= current
+ pathSum(a, b, c, i + 1,
n, k, on);
}
// Since jumps are available
// pathSum can be from current
// or adjacent array
switch (on) {
case 0:
sum = current
+ max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 0));
break;
case 1:
sum = current
+ max(pathSum(a, b, c, i + 1,
n, k - 1, 0),
max(pathSum(a, b, c, i + 1,
n, k, 1),
pathSum(a, b, c, i + 1,
n, k - 1, 2)));
break;
case 2:
sum = current
+ max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 2));
break;
}
return dp[on][i][k] = sum;
}
void findMaxSum(int* a, int* b,
int* c, int n, int k)
{
int sum = 0;
// Creating the DP array for memoization
initializeDp();
// Find the pathSum using recursive approach
for (int i = 0; i < 3; i++) {
// Maximise the sum
sum = max(sum,
pathSum(a, b, c, 0,
n, k, i));
}
cout << sum;
}
// Driver Code
int main()
{
int n = 5, k = 1;
int A[n] = { 4, 5, 1, 2, 10 };
int B[n] = { 9, 7, 3, 20, 16 };
int C[n] = { 6, 12, 13, 9, 8 };
findMaxSum(A, B, C, n, k);
return 0;
}
Java
// Java program to maximum path sum in
// the given arrays with at most K jumps
import java.util.*;
class GFG
{
static int M = 3;
static int N = 5;
static int K = 2;
static int dp[][][] = new int[M][N][K];
static void initializeDp()
{
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < K; k++)
dp[i][j][k] = -1;
}
// Function to calculate maximum path sum
static int pathSum(int a[], int b[], int c[],
int i, int n,
int k, int on)
{
// Base Case
if (i == n)
return 0;
if (dp[on][i][k] != -1)
return dp[on][i][k];
int current = 0, sum = 0;
switch (on) {
case 0:
current = a[i];
break;
case 1:
current = b[i];
break;
case 2:
current = c[i];
break;
}
// No jumps available.
// Hence pathSum can be
// from current array only
if (k == 0) {
return dp[on][i][k]
= current
+ pathSum(a, b, c, i + 1,
n, k, on);
}
// Since jumps are available
// pathSum can be from current
// or adjacent array
switch (on) {
case 0:
sum = current
+ Math.max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 0));
break;
case 1:
sum = current
+ Math.max(pathSum(a, b, c, i + 1,
n, k - 1, 0),
Math.max(pathSum(a, b, c, i + 1,
n, k, 1),
pathSum(a, b, c, i + 1,
n, k - 1, 2)));
break;
case 2:
sum = current
+ Math.max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 2));
break;
}
return dp[on][i][k] = sum;
}
static void findMaxSum(int a[], int b[],
int c[], int n, int k)
{
int sum = 0;
// Creating the DP array for memoization
initializeDp();
// Find the pathSum using recursive approach
for (int i = 0; i < 3; i++) {
// Maximise the sum
sum = Math.max(sum,
pathSum(a, b, c, 0,
n, k, i));
}
System.out.print(sum);
}
// Driver Code
public static void main(String []args)
{
int n = 5, k = 1;
int A[] = { 4, 5, 1, 2, 10 };
int B[] = { 9, 7, 3, 20, 16 };
int C[] = { 6, 12, 13, 9, 8 };
findMaxSum(A, B, C, n, k);
}
}
// This code is contributed by chitranayal
Python
#Python3 program to maximum path sum in #the given arrays with at most K jumps M = 3 N = 5 K = 2 dp=[[[-1 for i in range(K)] for i in range(N)] for i in range(M)] def initializeDp(): for i in range(M): for j in range(N): for k in range(K): dp[i][j][k] = -1 #Function to calculate maximum path sum def pathSum(a, b, c, i, n, k, on): #Base Case if (i == n): return 0 if (dp[on][i][k] != -1): return dp[on][i][k] current, sum = 0, 0 if on == 0: current = a[i] #break if on == 1: current = b[i] #break if on == 2: current = c[i] #break #No jumps available. #Hence pathSum can be #from current array only if (k == 0): dp[on][i][k] = current + pathSum(a, b, c, i + 1, n, k, on) return dp[on][i][k] #Since jumps are available #pathSum can be from current #or adjacent array if on == 0: sum = current + max(pathSum(a, b, c, i + 1, n, k - 1, 1), pathSum(a, b, c, i + 1, n, k, 0)) #break if on == 1: sum = current + max(pathSum(a, b, c, i + 1, n, k - 1, 0), max(pathSum(a, b, c, i + 1, n, k, 1), pathSum(a, b, c, i + 1, n, k - 1, 2))) #break if on == 2: sum = current + max(pathSum(a, b, c, i + 1, n, k - 1, 1), pathSum(a, b, c, i + 1, n, k, 2)) #break dp[on][i][k] = sum return sum def findMaxSum(a, b, c, n, k): sum = 0 #Creating the DP array for memoization initializeDp() #Find the pathSum using recursive approach for i in range(3): #Maximise the sum sum = max(sum, pathSum(a, b, c, 0, n, k, i)) print(sum) #Driver Code if __name__ == '__main__': n = 5 k = 1 A = [4, 5, 1, 2, 10] B = [9, 7, 3, 20, 16] C = [6, 12, 13, 9, 8] findMaxSum(A, B, C, n, k) #This code is contributed by Mohit Kumar 29
C#
// C# program to maximum path sum in
// the given arrays with at most K jumps
using System;
class GFG{
static int M = 3;
static int N = 5;
static int K = 2;
static int [,,]dp = new int[M, N, K];
static void initializeDp()
{
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < K; k++)
dp[i, j, k] = -1;
}
// Function to calculate maximum path sum
static int pathSum(int []a, int []b, int []c,
int i, int n,
int k, int on)
{
// Base Case
if (i == n)
return 0;
if (dp[on, i, k] != -1)
return dp[on, i, k];
int current = 0, sum = 0;
switch (on)
{
case 0:
current = a[i];
break;
case 1:
current = b[i];
break;
case 2:
current = c[i];
break;
}
// No jumps available.
// Hence pathSum can be
// from current array only
if (k == 0)
{
return dp[on, i, k] = current +
pathSum(a, b, c, i + 1,
n, k, on);
}
// Since jumps are available
// pathSum can be from current
// or adjacent array
switch (on)
{
case 0:
sum = current + Math.Max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 0));
break;
case 1:
sum = current + Math.Max(pathSum(a, b, c, i + 1,
n, k - 1, 0),
Math.Max(pathSum(a, b, c, i + 1,
n, k, 1),
pathSum(a, b, c, i + 1,
n, k - 1, 2)));
break;
case 2:
sum = current + Math.Max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 2));
break;
}
return dp[on, i, k] = sum;
}
static void findMaxSum(int []a, int []b,
int []c, int n, int k)
{
int sum = 0;
// Creating the DP array for memoization
initializeDp();
// Find the pathSum using recursive approach
for(int i = 0; i < 3; i++)
{
// Maximise the sum
sum = Math.Max(sum, pathSum(a, b, c, 0,
n, k, i));
}
Console.Write(sum);
}
// Driver Code
public static void Main(String []args)
{
int n = 5, k = 1;
int []A = { 4, 5, 1, 2, 10 };
int []B = { 9, 7, 3, 20, 16 };
int []C = { 6, 12, 13, 9, 8 };
findMaxSum(A, B, C, n, k);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to maximum path sum in
// the given arrays with at most K jumps
let M = 3;
let N = 5;
let K = 2;
let dp=new Array(M);
function initializeDp()
{
for (let i = 0; i < M; i++)
{
dp[i]=new Array(N);
for (let j = 0; j < N; j++)
{
dp[i][j]=new Array(K);
for (let k = 0; k < K; k++)
dp[i][j][k] = -1;
}
}
}
// Function to calculate maximum path sum
function pathSum(a,b,c,i,n,k,on)
{
// Base Case
if (i == n)
return 0;
if (dp[on][i][k] != -1)
return dp[on][i][k];
let current = 0, sum = 0;
switch (on) {
case 0:
current = a[i];
break;
case 1:
current = b[i];
break;
case 2:
current = c[i];
break;
}
// No jumps available.
// Hence pathSum can be
// from current array only
if (k == 0) {
return dp[on][i][k]
= current
+ pathSum(a, b, c, i + 1,
n, k, on);
}
// Since jumps are available
// pathSum can be from current
// or adjacent array
switch (on) {
case 0:
sum = current
+ Math.max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 0));
break;
case 1:
sum = current
+ Math.max(pathSum(a, b, c, i + 1,
n, k - 1, 0),
Math.max(pathSum(a, b, c, i + 1,
n, k, 1),
pathSum(a, b, c, i + 1,
n, k - 1, 2)));
break;
case 2:
sum = current
+ Math.max(pathSum(a, b, c, i + 1,
n, k - 1, 1),
pathSum(a, b, c, i + 1,
n, k, 2));
break;
}
return dp[on][i][k] = sum;
}
function findMaxSum(a,b,c,n,k)
{
let sum = 0;
// Creating the DP array for memoization
initializeDp();
// Find the pathSum using recursive approach
for (let i = 0; i < 3; i++) {
// Maximise the sum
sum = Math.max(sum,
pathSum(a, b, c, 0,
n, k, i));
}
document.write(sum);
}
// Driver Code
let n = 5, k = 1;
let A=[4, 5, 1, 2, 10];
let B=[9, 7, 3, 20, 16];
let C=[6, 12, 13, 9, 8 ];
findMaxSum(A, B, C, n, k);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
67
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N * K)
Publicación traducida automáticamente
Artículo escrito por abhinav mudgal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA