logo

TechCodeview

Sti med maksimal gjennomsnittsverdi

Gitt en kvadratisk matrise av størrelse N*N hvor hver celle er knyttet til en spesifikk kostnad. En bane er definert som en spesifikk sekvens av celler som starter fra den øverste venstre cellen beveger seg bare til høyre eller ned og ender i cellen nederst til høyre. Vi ønsker å finne en vei med maksimalt gjennomsnitt over alle eksisterende stier. Gjennomsnitt beregnes som totalkostnad delt på antall besøkte celler i banen. 

Eksempler:  

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

En interessant observasjon er at de eneste tillatte trekkene er nede, og til høyre trenger vi N-1 nedtrekk og N-1 høyretrekk for å nå målet (nederst til høyre). Så enhver vei fra øverste venstre hjørne til nederste høyre hjørne krever 2N - 1 celler. I gjennomsnittlig verdi nevneren er fast og vi trenger bare å maksimere telleren. Derfor må vi i utgangspunktet finne den maksimale sumveien. Å beregne maksimal sum av banen er et klassisk dynamisk programmeringsproblem hvis dp[i][j] representerer maksimal sum til celle (i j) fra (0 0), så oppdaterer vi ved hver celle (i j) dp[i][j] som nedenfor



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

Når vi får maksimal sum av alle stier, deler vi denne summen med (2N - 1), og vi vil få vårt maksimale gjennomsnitt. 

Implementering:

C++ 
//C/C++ program to find maximum average cost path #include    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 import java.io.*; 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.
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+1N+1];  dp[00] = cost[00];    /* Initialize first column of total cost(dp)  array */  for (int i = 1; i < N; i++)  dp[i 0] = dp[i - 10] + cost[i 0];    /* Initialize first row of dp array */  for (int j = 1; j < N; j++)  dp[0 j] = dp[0j - 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[ij - 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.
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>
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 ?>
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.

Produksjon 
5.200000

Tidskompleksitet : O(N2) for gitt inndata N
Hjelpeplass: PÅ2) for gitt inngang N.

Metode - 2: Uten å bruke Ekstra N*N mellomrom 

Vi kan bruke input cost array som en dp for å lagre ans. så på denne måten trenger vi ikke en ekstra dp-array eller ikke den ekstra plassen.

En observasjon er at de eneste tillatte trekkene er nedover og til høyre trenger vi N-1 nedtrekk og N-1 høyretrekk for å nå målet (nederst til høyre). Så enhver bane fra øverste venstre hjørne til nederste høyre hjørne krever 2N - 1 celle. I gjennomsnittlig verdi nevneren er fast og vi trenger bare å maksimere telleren. Derfor må vi i utgangspunktet finne den maksimale sumveien. Å beregne maksimal sum av banen er et klassisk dynamisk programmeringsproblem. Vi trenger heller ikke noen prev cost[i][j] verdi etter å ha beregnet dp[i][j] slik at vi kan endre kostnads[i][j] verdien slik at vi ikke trenger ekstra plass for dp[i][j].

for all i 1 <= i < N  
 cost[i][0] = cost[i-1][0] + cost[i][0];   
for all j 1 <= j < N  
 cost[0][j] = cost[0][j-1] + cost[0][j];   
otherwise   
 cost[i][j] = max(cost[i-1][j] cost[i][j-1]) + cost[i][j];

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++ 
// C++ program to find maximum average cost path #include    using namespace std; // Method returns maximum average of all path of cost matrix double maxAverageOfPath(vector<vector<int>>cost) {  int N = cost.size();  // Initialize first column of total cost array  for (int i = 1; i < N; i++)  cost[i][0] = cost[i][0] + cost[i - 1][0];  // Initialize first row of array  for (int j = 1; j < N; j++)  cost[0][j] = cost[0][j - 1] + cost[0][j];  // Construct rest of the array  for (int i = 1; i < N; i++)  for (int j = 1; j <= N; j++)  cost[i][j] = max(cost[i - 1][j] cost[i][j - 1]) + cost[i][j];  // divide maximum sum by constant path  // length : (2N - 1) for getting average  return (double)cost[N - 1][N - 1] / (2 * N - 1); } // Driver program int main() {  vector<vector<int>> cost = {{1 2 3}  {6 5 4}  {7 3 9}  };  cout << maxAverageOfPath(cost);  return 0; }
Java 
// Java program to find maximum average cost path import java.io.*; class GFG {  // Method returns maximum average of all path of cost  // matrix  static double maxAverageOfPath(int[][] cost)  {  int N = cost.length;  // Initialize first column of total cost array  for (int i = 1; i < N; i++)  cost[i][0] = cost[i][0] + cost[i - 1][0];  // Initialize first row of array  for (int j = 1; j < N; j++)  cost[0][j] = cost[0][j - 1] + cost[0][j];  // Construct rest of the array  for (int i = 1; i < N; i++)  for (int j = 1; j < N; j++)  cost[i][j] = Math.max(cost[i - 1][j]  cost[i][j - 1])  + cost[i][j];  // divide maximum sum by constant path  // length : (2N - 1) for getting average  return (double)cost[N - 1][N - 1] / (2 * N - 1);  }  // Driver program  public static void main(String[] args)  {  int[][] cost  = { { 1 2 3 } { 6 5 4 } { 7 3 9 } };  System.out.println(maxAverageOfPath(cost));  } } // This code is contributed by karandeep1234
C# 
// C# program to find maximum average cost path using System; class GFG {  // Method returns maximum average of all path of cost  // matrix  static double maxAverageOfPath(int[ ] cost)  {  int N = cost.GetLength(0);  // Initialize first column of total cost array  for (int i = 1; i < N; i++)  cost[i 0] = cost[i 0] + cost[i - 1 0];  // Initialize first row of array  for (int j = 1; j < N; j++)  cost[0 j] = cost[0 j - 1] + cost[0 j];  // Construct rest of the array  for (int i = 1; i < N; i++)  for (int j = 1; j < N; j++)  cost[i j] = Math.Max(cost[i - 1 j]  cost[i j - 1])  + cost[i j];  // divide maximum sum by constant path  // length : (2N - 1) for getting average  return (double)cost[N - 1 N - 1] / (2 * N - 1);  }  // Driver program  static void Main(string[] args)  {  int[ ] cost  = { { 1 2 3 } { 6 5 4 } { 7 3 9 } };  Console.WriteLine(maxAverageOfPath(cost));  } } // This code is contributed by karandeep1234
JavaScript 
// Method returns maximum average of all path of cost matrix function maxAverageOfPath(cost) {  let N = cost.length;  // Initialize first column of total cost array  for (let i = 1; i < N; i++)  cost[i][0] = cost[i][0] + cost[i - 1][0];  // Initialize first row of array  for (let j = 1; j < N; j++)  cost[0][j] = cost[0][j - 1] + cost[0][j];  // Construct rest of the array  for (let i = 1; i < N; i++)  for (let j = 1; j <= N; j++)  cost[i][j] = Math.max(cost[i - 1][j] cost[i][j - 1]) + cost[i][j];  // divide maximum sum by constant path  // length : (2N - 1) for getting average  return (cost[N - 1][N - 1]) / (2.0 * N - 1); } // Driver program let cost = [[1 2 3]  [6 5 4]  [7 3 9]]; console.log(maxAverageOfPath(cost)) // This code is contributed by karandeep1234.
Python3 
# Python program to find maximum average cost path from typing import List def maxAverageOfPath(cost: List[List[int]]) -> float: N = len(cost) # Initialize first column of total cost array for i in range(1 N): cost[i][0] = cost[i][0] + cost[i - 1][0] # Initialize first row of array for j in range(1 N): cost[0][j] = cost[0][j - 1] + cost[0][j] # Construct rest of the array for i in range(1 N): for j in range(1 N): cost[i][j] = max(cost[i - 1][j] cost[i][j - 1]) + cost[i][j] # divide maximum sum by constant path # length : (2N - 1) for getting average return cost[N - 1][N - 1] / (2 * N - 1) # Driver program def main(): cost = [[1 2 3] [6 5 4] [7 3 9]] print(maxAverageOfPath(cost)) if __name__ == '__main__': main()

Produksjon 
5.2

Tidskompleksitet: O(N*N)
Hjelpeplass: O(1)