Dada una array cuadrada de tamaño N*N, donde cada celda tiene asociado un costo específico. Una ruta se define como una secuencia específica de celdas que comienza en la celda superior izquierda, se mueve solo hacia la derecha o hacia abajo y termina en la celda inferior derecha. Queremos encontrar un camino con el promedio máximo sobre todos los caminos existentes. El promedio se calcula como el costo total dividido por el número de celdas visitadas en la ruta.
Ejemplos:
Input : Matrix = [1, 2, 3
4, 5, 6
7, 8, 9]
Output : 5.8
Path with maximum average is, 1 -> 4 -> 7 -> 8 -> 9
Sum of the path is 29 and average is 29/5 = 5.8
Una observación interesante es que los únicos movimientos permitidos son hacia abajo y hacia la derecha, necesitamos N-1 movimientos hacia abajo y N-1 movimientos hacia la derecha para llegar al destino (extremo inferior derecho). Entonces, cualquier ruta desde la esquina superior izquierda hasta la esquina inferior derecha requiere 2N – 1 celdas. En valor promedio, el denominador es fijo y solo necesitamos maximizar el numerador. Por lo tanto, básicamente necesitamos encontrar la ruta de suma máxima. Calcular la suma máxima de la ruta es un problema clásico de programación dinámica, si dp[i][j] representa la suma máxima hasta la celda (i, j) desde (0, 0), entonces en cada celda (i, j), actualizamos dp[ i][j] como se muestra a continuación,
for all i, 1 <= i <= N dp[i][0] = dp[i-1][0] + cost[i][0]; for all j, 1 <= j <= N dp[0][j] = dp[0][j-1] + cost[0][j]; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j];
Una vez que obtengamos la suma máxima de todos los caminos, dividiremos esta suma por (2N – 1) y obtendremos nuestro promedio máximo.
Implementación:
C++
// C/C++ program to find maximum average cost path
#include <bits/stdc++.h>
using namespace std;
// Maximum number of rows and/or columns
const int M = 100;
// method returns maximum average of all path of
// cost matrix
double maxAverageOfPath(int cost[M][M], int N)
{
int dp[N+1][N+1];
dp[0][0] = cost[0][0];
/* Initialize first column of total cost(dp) array */
for (int i = 1; i < N; i++)
dp[i][0] = dp[i-1][0] + cost[i][0];
/* Initialize first row of dp array */
for (int j = 1; j < N; j++)
dp[0][j] = dp[0][j-1] + cost[0][j];
/* Construct rest of the dp array */
for (int i = 1; i < N; i++)
for (int j = 1; j <= N; j++)
dp[i][j] = max(dp[i-1][j],
dp[i][j-1]) + cost[i][j];
// divide maximum sum by constant path
// length : (2N - 1) for getting average
return (double)dp[N-1][N-1] / (2*N-1);
}
/* Driver program to test above functions */
int main()
{
int cost[M][M] = { {1, 2, 3},
{6, 5, 4},
{7, 3, 9}
};
printf("%f", maxAverageOfPath(cost, 3));
return 0;
}
Java
// JAVA Code for Path with maximum average
// value
class GFG {
// method returns maximum average of all
// path of cost matrix
public static double maxAverageOfPath(int cost[][],
int N)
{
int dp[][] = new int[N+1][N+1];
dp[0][0] = cost[0][0];
/* Initialize first column of total cost(dp)
array */
for (int i = 1; i < N; i++)
dp[i][0] = dp[i-1][0] + cost[i][0];
/* Initialize first row of dp array */
for (int j = 1; j < N; j++)
dp[0][j] = dp[0][j-1] + cost[0][j];
/* Construct rest of the dp array */
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
dp[i][j] = Math.max(dp[i-1][j],
dp[i][j-1]) + cost[i][j];
// divide maximum sum by constant path
// length : (2N - 1) for getting average
return (double)dp[N-1][N-1] / (2 * N - 1);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int cost[][] = {{1, 2, 3},
{6, 5, 4},
{7, 3, 9}};
System.out.println(maxAverageOfPath(cost, 3));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python program to find # maximum average cost path # Maximum number of rows # and/or columns M = 100 # method returns maximum average of # all path of cost matrix def maxAverageOfPath(cost, N): dp = [[0 for i in range(N + 1)] for j in range(N + 1)] dp[0][0] = cost[0][0] # Initialize first column of total cost(dp) array for i in range(1, N): dp[i][0] = dp[i - 1][0] + cost[i][0] # Initialize first row of dp array for j in range(1, N): dp[0][j] = dp[0][j - 1] + cost[0][j] # Construct rest of the dp array for i in range(1, N): for j in range(1, N): dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + cost[i][j] # divide maximum sum by constant path # length : (2N - 1) for getting average return dp[N - 1][N - 1] / (2 * N - 1) # Driver program to test above function cost = [[1, 2, 3], [6, 5, 4], [7, 3, 9]] print(maxAverageOfPath(cost, 3)) # This code is contributed by Soumen Ghosh.
C#
// C# Code for Path with maximum average
// value
using System;
class GFG {
// method returns maximum average of all
// path of cost matrix
public static double maxAverageOfPath(int [,]cost,
int N)
{
int [,]dp = new int[N+1,N+1];
dp[0,0] = cost[0,0];
/* Initialize first column of total cost(dp)
array */
for (int i = 1; i < N; i++)
dp[i, 0] = dp[i - 1,0] + cost[i, 0];
/* Initialize first row of dp array */
for (int j = 1; j < N; j++)
dp[0, j] = dp[0,j - 1] + cost[0, j];
/* Construct rest of the dp array */
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
dp[i, j] = Math.Max(dp[i - 1, j],
dp[i,j - 1]) + cost[i, j];
// divide maximum sum by constant path
// length : (2N - 1) for getting average
return (double)dp[N - 1, N - 1] / (2 * N - 1);
}
// Driver Code
public static void Main()
{
int [,]cost = {{1, 2, 3},
{6, 5, 4},
{7, 3, 9}};
Console.Write(maxAverageOfPath(cost, 3));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// Php program to find maximum average cost path
// method returns maximum average of all path of
// cost matrix
function maxAverageOfPath($cost, $N)
{
$dp = array(array()) ;
$dp[0][0] = $cost[0][0];
/* Initialize first column of total cost(dp) array */
for ($i = 1; $i < $N; $i++)
$dp[$i][0] = $dp[$i-1][0] + $cost[$i][0];
/* Initialize first row of dp array */
for ($j = 1; $j < $N; $j++)
$dp[0][$j] = $dp[0][$j-1] + $cost[0][$j];
/* Construct rest of the dp array */
for ($i = 1; $i < $N; $i++)
{
for ($j = 1; $j <= $N; $j++)
$dp[$i][$j] = max($dp[$i-1][$j],$dp[$i][$j-1]) + $cost[$i][$j];
}
// divide maximum sum by constant path
// length : (2N - 1) for getting average
return $dp[$N-1][$N-1] / (2*$N-1);
}
// Driver code
$cost = array(array(1, 2, 3),
array( 6, 5, 4),
array(7, 3, 9) ) ;
echo maxAverageOfPath($cost, 3) ;
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript Code for Path with maximum average value
// method returns maximum average of all
// path of cost matrix
function maxAverageOfPath(cost, N)
{
let dp = new Array(N+1);
for (let i = 0; i < N + 1; i++)
{
dp[i] = new Array(N + 1);
for (let j = 0; j < N + 1; j++)
{
dp[i][j] = 0;
}
}
dp[0][0] = cost[0][0];
/* Initialize first column of total cost(dp)
array */
for (let i = 1; i < N; i++)
dp[i][0] = dp[i-1][0] + cost[i][0];
/* Initialize first row of dp array */
for (let j = 1; j < N; j++)
dp[0][j] = dp[0][j-1] + cost[0][j];
/* Construct rest of the dp array */
for (let i = 1; i < N; i++)
for (let j = 1; j < N; j++)
dp[i][j] = Math.max(dp[i-1][j],
dp[i][j-1]) + cost[i][j];
// divide maximum sum by constant path
// length : (2N - 1) for getting average
return dp[N-1][N-1] / (2 * N - 1);
}
let cost = [[1, 2, 3],
[6, 5, 4],
[7, 3, 9]];
document.write(maxAverageOfPath(cost, 3));
</script>
5.200000
Complejidad de tiempo : O(N 2 ) para entrada dada N
Espacio auxiliar: O(N 2 ) para entrada dada N.
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA