Pad met maximale gemiddelde waarde
Gegeven een vierkante matrix van grootte N*N waarbij elke cel is gekoppeld aan specifieke kosten. Een pad wordt gedefinieerd als een specifieke reeks cellen die begint bij de cel linksboven, alleen naar rechts of naar beneden beweegt en eindigt in de cel rechtsonder. We willen een pad vinden met het maximale gemiddelde over alle bestaande paden. Het gemiddelde wordt berekend als de totale kosten gedeeld door het aantal bezochte cellen in het pad.
Voorbeelden:
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
Een interessante observatie is dat de enige toegestane bewegingen naar beneden en naar rechts zijn. We hebben N-1 bewegingen naar beneden en N-1 bewegingen naar rechts nodig om de bestemming te bereiken (uiterst rechtsonder). Voor elk pad van de linkerbovenhoek naar de rechteronderhoek zijn dus 2N - 1 cellen nodig. In gemiddeld waarde, de noemer staat vast en we moeten de teller gewoon maximaliseren. Daarom moeten we in principe het maximale sompad vinden. Het berekenen van de maximale som van het pad is een klassiek dynamisch programmeerprobleem als dp[i][j] de maximale som vertegenwoordigt tot cel (ij) vanaf (0 0), dan werken we bij elke cel (ij) dp[i][j] bij, zoals hieronder
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];
Zodra we de maximale som van alle paden hebben, delen we deze som door (2N - 1) en krijgen we ons maximale gemiddelde.
Uitvoering:
C++Java//C/C++ program to find maximum average cost path #includeusing 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 ; } C#// 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.JavaScript// 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< 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>Python3// 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 ?>
Uitvoer5.200000Tijdcomplexiteit : OP 2 ) voor gegeven invoer N
Hulpruimte: OP 2 ) voor gegeven invoer N.Methode - 2: Zonder extra N*N-ruimte te gebruiken
We kunnen de invoerkostenarray gebruiken als een dp om de ans op te slaan. dus op deze manier hebben we geen extra dp-array of geen extra ruimte nodig.
Eén observatie is dat de enige toegestane bewegingen naar beneden en naar rechts zijn. We hebben N-1 bewegingen naar beneden en N-1 bewegingen naar rechts nodig om de bestemming te bereiken (uiterst rechtsonder). Voor elk pad van de linkerbovenhoek naar de rechteronderhoek is dus 2N - 1 cel nodig. In gemiddeld waarde, de noemer staat vast en we moeten de teller gewoon maximaliseren. Daarom moeten we in principe het maximale sompad vinden. Het berekenen van de maximale som van het pad is een klassiek dynamisch programmeerprobleem. We hebben ook geen vorige cost[i][j]-waarde nodig na het berekenen van dp[i][j], dus we kunnen de cost[i][j]-waarde zodanig wijzigen dat we geen extra ruimte nodig hebben voor 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];
Hieronder vindt u de implementatie van de bovenstaande aanpak:
C++Java// C++ program to find maximum average cost path #includeusing 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 ; } C#// 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 karandeep1234JavaScript// 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 karandeep1234Python3// 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.
Uitvoer5.2Tijdcomplexiteit: O(N*N)
Hulpruimte: O(1)
