Adott egy N*N méretű négyzetmátrix, ahol minden cellához egy adott költség tartozik. Az útvonal a cellák meghatározott sorozata, amely a bal felső cellától kezdődik, csak jobbra vagy lefelé mozog, és a jobb alsó cellában ér véget. Olyan útvonalat akarunk találni, amely a létező útvonalak maximális átlagával rendelkezik. Az átlagot úgy számítják ki, hogy a teljes költséget elosztják az útvonalon meglátogatott cellák számával.
Példák:
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
Egy érdekes megfigyelés, hogy az egyetlen megengedett mozgás lefelé, és jobbra van szükség N-1 lefelé és N-1 jobbra, hogy elérjük a célt (jobbra lent). Tehát a bal felső saroktól a jobb alsó sarokhoz vezető útvonalak 2N - 1 cellát igényelnek. In átlagos érték esetén a nevező rögzített, és csak maximalizálnunk kell a számlálót. Ezért alapvetően meg kell találnunk a maximális összeg elérési utat. Az útvonal maximális összegének kiszámítása klasszikus dinamikus programozási probléma, ha dp[i][j] a maximális összeget jelenti az (i j) celláig (0 0) akkor minden cellában (i j) frissítjük a dp[i][j] értéket az alábbiak szerint.
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];
Miután megkaptuk az összes útvonal maximális összegét, elosztjuk ezt az összeget (2N - 1) és megkapjuk a maximális átlagunkat.
Végrehajtás:
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.
Kimenet
5.200000
Időbeli összetettség : O(N2) adott N bemenethez
Kiegészítő tér: ON2) adott N bemenetre.
2. módszer: Extra N*N tér használata nélkül
Használhatjuk a bemeneti költség tömböt dp-ként az ans tárolására. így így nincs szükségünk extra dp tömbre, vagy nincs szükségünk extra helyre.
Az egyik megfigyelés az, hogy az egyetlen megengedett mozgás lefelé és jobbra van szükségünk N-1 lefelé és N-1 jobbra lépésre, hogy elérjük a célt (jobbra lent). Tehát a bal felső saroktól a jobb alsó sarokig tartó bármely útvonalhoz 2N - 1 cella szükséges. In átlagos érték esetén a nevező rögzített, és csak maximalizálnunk kell a számlálót. Ezért alapvetően meg kell találnunk a maximális összeg elérési utat. Az útvonal maximális összegének kiszámítása egy klasszikus dinamikus programozási probléma, ráadásul a dp[i][j] kiszámítása után nincs szükségünk korábbi költség[i][j] értékre, így a költség[i][j] értéket úgy módosíthatjuk, hogy ne kelljen több hely a dp[i][j] számára.
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];
Az alábbiakban bemutatjuk a fenti megközelítés megvalósítását:
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()
Kimenet
5.2
Időbeli összetettség: O(N*N)
Kiegészítő tér: O(1)