Podana je kvadratna matrika velikosti N*N, kjer je vsaka celica povezana z določeno ceno. Pot je opredeljena kot določeno zaporedje celic, ki se začne od zgornje leve celice in se premika samo desno ali navzdol in konča v spodnji desni celici. Želimo najti pot z največjim povprečjem med vsemi obstoječimi potmi. Povprečje se izračuna kot skupni stroški, deljeni s številom celic, obiskanih na poti.
Primeri:
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
Ena zanimiva ugotovitev je, da sta edini dovoljeni potezi navzdol in desno, potrebujemo N-1 potez navzdol in N-1 potez desno, da dosežemo cilj (skrajno desno spodaj). Vsaka pot od zgornjega levega kota do spodnjega desnega kota torej zahteva 2N - 1 celic. notri povprečje vrednost je imenovalec fiksen in samo povečati moramo števec. Zato moramo v bistvu najti pot največje vsote. Izračun največje vsote poti je klasični problem dinamičnega programiranja, če dp[i][j] predstavlja največjo vsoto do celice (i j) od (0 0), nato pa v vsaki celici (i j) posodobimo dp[i][j] kot spodaj
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];
Ko dobimo največjo vsoto vseh poti, bomo to vsoto delili z (2N - 1) in dobili bomo naše največje povprečje.
Izvedba:
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.
Izhod
5.200000
Časovna zapletenost : O(N2) za podan vnos N
Pomožni prostor: O(N2) za dani vhod N.
Metoda - 2: Brez uporabe dodatnega prostora N*N
Kot dp za shranjevanje ans lahko uporabimo niz vhodnih stroškov. tako da na ta način ne potrebujemo dodatnega polja dp ali ne dodatnega prostora.
Ena ugotovitev je, da sta dovoljeni samo potezi navzdol in desno, potrebujemo N-1 potez navzdol in N-1 potez desno, da dosežemo cilj (skrajno desno spodaj). Vsaka pot od zgornjega levega kota do spodnjega desnega kota torej zahteva 2N - 1 celico. noter povprečje vrednost je imenovalec fiksen in samo povečati moramo števec. Zato moramo v bistvu najti pot največje vsote. Izračun največje vsote poti je klasični problem dinamičnega programiranja, prav tako ne potrebujemo nobene prejšnje vrednosti cost[i][j] po izračunu dp[i][j], tako da lahko spremenimo vrednost cost[i][j] tako, da ne potrebujemo dodatnega prostora 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];
Spodaj je izvedba zgornjega pristopa:
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()
Izhod
5.2
Časovna zapletenost: O(N*N)
Pomožni prostor: O(1)