المسار ذو القيمة المتوسطة القصوى
بالنظر إلى مصفوفة مربعة بحجم N*N حيث ترتبط كل خلية بتكلفة محددة. يتم تعريف المسار على أنه تسلسل محدد من الخلايا يبدأ من الخلية العلوية اليسرى ويتحرك لليمين أو للأسفل فقط وينتهي في الخلية اليمنى السفلية. نريد العثور على مسار بأقصى متوسط على جميع المسارات الموجودة. يتم حساب المتوسط كتكلفة إجمالية مقسومة على عدد الخلايا التي تمت زيارتها في المسار.
أمثلة:
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
إحدى الملاحظات المثيرة للاهتمام هي أن التحركات الوحيدة المسموح بها هي للأسفل وعلى اليمين نحتاج إلى تحركات N-1 لأسفل وحركات N-1 لليمين للوصول إلى الوجهة (أسفل أقصى اليمين). لذا فإن أي مسار من الزاوية اليسرى العليا إلى الزاوية اليمنى السفلية يتطلب 2N - 1 من الخلايا. في متوسط القيمة أن المقام ثابت ونحتاج فقط إلى تعظيم البسط. لذلك نحن بحاجة بشكل أساسي إلى العثور على الحد الأقصى لمسار المجموع. يعد حساب الحد الأقصى لمجموع المسار مشكلة برمجة ديناميكية كلاسيكية إذا كان dp[i][j] يمثل الحد الأقصى لمجموع حتى الخلية (i j) من (0 0) ثم في كل خلية (i j) نقوم بتحديث dp[i][j] على النحو التالي
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];
بمجرد أن نحصل على الحد الأقصى لمجموع جميع المسارات، سنقسم هذا المجموع على (2N - 1) وسنحصل على الحد الأقصى لمتوسطنا.
تطبيق:
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 ?>
الإخراج5.200000تعقيد الوقت : على 2 ) للإدخال المحدد N
المساحة المساعدة: على 2 ) لإدخال معين N.الطريقة - 2: بدون استخدام مساحة N*N إضافية
يمكننا استخدام مصفوفة تكلفة الإدخال باعتبارها dp لتخزين الإجابة. وبهذه الطريقة لا نحتاج إلى مصفوفة dp إضافية أو لا نحتاج إلى تلك المساحة الإضافية.
إحدى الملاحظات هي أن التحركات الوحيدة المسموح بها هي للأسفل وعلى اليمين نحتاج إلى تحركات N-1 لأسفل وحركات N-1 لليمين للوصول إلى الوجهة (أسفل أقصى اليمين). لذا فإن أي مسار من الزاوية اليسرى العليا إلى الزاوية اليمنى السفلية يتطلب 2N - 1 خلية. في متوسط القيمة أن المقام ثابت ونحتاج فقط إلى تعظيم البسط. لذلك نحن بحاجة بشكل أساسي إلى العثور على الحد الأقصى لمسار المجموع. يعد حساب الحد الأقصى لمجموع المسار مشكلة برمجة ديناميكية كلاسيكية، كما أننا لا نحتاج إلى أي قيمة تكلفة [i] [j] سابقة بعد حساب dp [i] [j] حتى نتمكن من تعديل قيمة التكلفة [i] [j] بحيث لا نحتاج إلى مساحة إضافية لـ 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];
وفيما يلي تنفيذ النهج المذكور أعلاه:
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.
الإخراج5.2تعقيد الوقت: يا (ن * ن)
المساحة المساعدة: يا(1)
