المسار مع متوسط ​​القيمة القصوى


مستوى الصعوبة سهل
كثيرا ما يطلب في سيسكو نظم ملحمة رمادي مختبرات 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] = [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

كود جافا للمسار بأقصى قيمة متوسطة

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) نظرًا لأننا اجتازنا ببساطة مصفوفة الإدخال. واستغرق الانتقال في موانئ دبي وقتًا فقط (1).

تعقيد الفضاء

O (N ^ 2) منذ أن أنشأنا مجموعة ثنائية الأبعاد DP.