Dana je kvadratna matrica veličine N*N gdje je svaka ćelija povezana s određenim troškom. Put je definiran kao određeni niz ćelija koji počinje od gornje lijeve ćelije i pomiče se samo desno ili dolje i završava u donjoj desnoj ćeliji. Želimo pronaći put s maksimalnim prosjekom svih postojećih puteva. Prosjek se izračunava kao ukupni trošak podijeljen s brojem ćelija posjećenih na putu.
Primjeri:
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
Jedno zanimljivo zapažanje je da su jedini dopušteni pokreti dolje i desno, trebamo N-1 dolje i N-1 desno da bismo došli do odredišta (dolje desno). Dakle, svaki put od gornjeg lijevog kuta do donjeg desnog kuta zahtijeva 2N - 1 ćelija. U prosjek vrijednost nazivnik je fiksan i trebamo samo maksimizirati brojnik. Stoga u osnovi trebamo pronaći put najvećeg zbroja. Izračunavanje maksimalnog zbroja puta klasični je problem dinamičkog programiranja ako dp[i][j] predstavlja maksimalni zbroj do ćelije (i j) od (0 0), tada u svakoj ćeliji (i j) ažuriramo dp[i][j] kao ispod
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];
Kada dobijemo maksimalni zbroj svih putanja, podijelit ćemo ovaj zbroj sa (2N - 1) i dobit ćemo naš maksimalni prosjek.
Implementacija:
C++//C/C++ program to find maximum average cost path #include
// 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# 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.
<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 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 ?> # 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.
Izlaz
5.200000
Vremenska složenost : O(N2) za dani unos N
Pomoćni prostor: NA2) za dati ulaz N.
Metoda - 2: Bez korištenja dodatnog N*N prostora
Možemo koristiti niz ulaznih troškova kao dp za pohranu ans. tako da nam na ovaj način ne treba dodatni dp niz ili nema tog dodatnog prostora.
Jedno zapažanje je da su jedini dopušteni pokreti dolje i desno, trebamo N-1 dolje i N-1 desno da bismo došli do odredišta (dolje desno). Dakle, svaki put od gornjeg lijevog kuta do donjeg desnog kuta zahtijeva 2N - 1 ćeliju. U prosjek vrijednost nazivnik je fiksan i trebamo samo maksimizirati brojnik. Stoga u osnovi trebamo pronaći put najvećeg zbroja. Izračunavanje maksimalnog zbroja puta je klasični problem dinamičkog programiranja također nam ne treba nikakva prethodna vrijednost cost[i][j] nakon izračuna dp[i][j] tako da možemo modificirati vrijednost cost[i][j] tako da nam ne treba dodatni prostor za 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];
U nastavku je implementacija gornjeg pristupa:
C++// C++ program to find maximum average cost path #include
// 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# 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
// 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.
# 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()
Izlaz
5.2
Vremenska složenost: O(N*N)
Pomoćni prostor: O(1)