Tutorialspoint.dev

Path with maximum average value

Given a square matrix of size N*N, where each cell is associated with a specific cost. A path is defined as a specific sequence of cells which starts from top left cell move only right or down and ends on bottom right cell. We want to find a path with maximum average over all existing paths. Average is computed as total cost divided by number of cells visited in path.
Examples:

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



One interesting observation is, the only allowed moves are down and right, we need N-1 down moves and N-1 right moves to reach destination (bottom rightmost). So any path from from top left corner to bottom right corner requires 2N – 1 cells. In average value, denominator is fixed and we need to just maximize numerator. Therefore we basically need to to find maximum sum path. Calculating maximum sum of path is a classic dynamic programming problem, if dp[i][j] represents maximum sum till cell (i, j) from (0, 0) then at each cell (i, j), we update dp[i][j] as below,

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]; 

Once we get maximum sum of all paths we will divide this sum by (2N – 1) and we will get our maximum average.

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 costant 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
?>


Output:

5.2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter