נתיב עם ערך ממוצע מרבי


רמת קושי קַל
נשאל לעתים קרובות סיסקו מערכות אפיות גריי אורנג ' מעבדות SAP פעמים באינטרנט
מערך תכנות דינמי מַטרִיצָה

הצהרת בעיה

הבעיה "נתיב עם ערך ממוצע מרבי" קובעת שקיבלתם מערך דו-ממדי או מטריצה ​​של מספרים שלמים. שקול עכשיו שאתה עומד בתא השמאלי העליון וצריך להגיע מימין למטה. כדי להגיע ליעד, עליך להתקדם בכיוון התחתון או בכיוון הנכון. לפי יעד, כאן אנו מתכוונים לתא מימין למטה. תנאי אחד קיים, שאתה צריך לעבור בדרך כזו שנותנת לנו ערך ממוצע מרבי.

דוגמה

3 3 // number of rows and columns
1 1 2
10 1 100
10 10 1
22.6

הסבר

נתיב עם ערך ממוצע מרבי

עברנו מהתא השמאלי העליון באופן הבא: 1-> 10-> 1-> 100-> 1. אז הוספת זה מעלה לנו סכום כולל של 113. כך הממוצע הופך לשווה 113/5 = 22.6

גישה

אפשר לבוא בגישה של כוח אכזרי, שהיא יצירת כל הדרכים האפשריות להגיע לתא הימני התחתון. ברגע שיצרת את כל הנתיבים. עכשיו עברו עליהם ומצאו את סכום המספרים השלמים שנמצאים על הנתיב. אז ברגע שיש לך את כל הסכומים. מצא את הסכום המקסימלי בין אלה.

אך השימוש בגישה זו בטוח יעבור ל- TLE או יעלה על מגבלת הזמן. מכיוון שייצור מסלולים כאלה יוביל למורכבות זמן אקספוננציאלית. לכן, כדי לפתור את הבעיה במגבלות זמן. עלינו למצוא פיתרון יעיל. אבל, איך נוכל לעשות זאת? אנו יכולים לעשות זאת באמצעות תכנות דינמי. והבעיה גם דומה מאוד לבעיית סכום הנתיב המרבי. בבעיה זו, עלינו למצוא את סכום הנתיב המרבי במערך דו-ממדי. אותו הדבר אנחנו הולכים לעשות, אבל בסופו של דבר ניקח את הממוצע.

אז בשביל תכנות דינמי גִישָׁה. ניצור מערך DP דו-ממדי שבו כל תא במדריך DP יציין את הסכום המקסימלי שניתן להשיג אם נצטרך להתחיל מהפינה השמאלית העליונה לתא הנוכחי. כדי שנוכל לכתוב יחס חוזר כללי.

// תיקי בסיס
dp [0] [0] = a [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // הנה אני מתחיל מהשורה הראשונה עד השורה האחרונה של המטריצה
dp [0] [i] = dp [0] [i-1] + a [0] [i] // כאן אני מתחיל מהעמודה הראשונה עד העמודה האחרונה של המטריצה
// יחס הישנות
dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]) + a [i] [j] // לכל שאר התאים

קוד C ++ עבור נתיב עם ערך ממוצע מרבי

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int n,m; // number of rows and columns in input matrix
  cin>>n>>m;

  int input[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)
      cin>>input[i][j];
  }

  int dp[n][m];
  dp[0][0] = input[0][0];
  for(int i=1;i<n;i++)
    dp[i][0] = dp[i-1][0] + input[i][0];
  for(int i=1;i<m;i++)
    dp[0][i] = dp[0][i-1] + input[0][i];

  for(int i=1;i<n;i++){
    for(int j=1;j<m;j++)
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + input[i][j];
  }

  // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
  cout<<(dp[n-1][m-1]/((double)n+m-1));
}
3 3
1 1 2
10 1 100
10 10 1
22.6

קוד Java עבור נתיב עם ערך ממוצע מרבי

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); int m = sc.nextInt(); // number of rows and columns in input matrix

    int input[][] = new int[n][m];
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)
        input[i][j] = sc.nextInt();
    }

    int dp[][] = new int[n][m];
    dp[0][0] = input[0][0];
    for(int i=1;i<n;i++)
      dp[i][0] = dp[i-1][0] + input[i][0];
    for(int i=1;i<m;i++)
      dp[0][i] = dp[0][i-1] + input[0][i];

    for(int i=1;i<n;i++){
      for(int j=1;j<m;j++)
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + input[i][j];
    }

    // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
    System.out.print(dp[n-1][m-1]/((double)n+m-1));
  }
}
3 3
1 1 2
10 1 100
10 10 1
22.6

ניתוח מורכבות

מורכבות זמן

O (N ^ 2) מכיוון שפשוט עברנו מעל מערך הקלט. והמעבר ב- DP שלנו לקח רק זמן O (1).

מורכבות בחלל

O (N ^ 2) מאז שיצרנו מערך DP דו-ממדי.