जास्तीत जास्त सरासरी मूल्यासह पथ


अडचण पातळी सोपे
वारंवार विचारले सिस्को एपिक सिस्टम ग्रेऑरेंज एसएपी लॅब टाइम्स इंटरनेट
अरे डायनॅमिक प्रोग्रामिंग मॅट्रिक्स

समस्या विधान

“जास्तीत जास्त सरासरी मूल्यासह पथ” ही समस्या सांगते की आपल्याला 2 डी अ‍ॅरे किंवा पूर्णांकांची मॅट्रिक्स दिली आहे. आता आपण वरच्या-डाव्या सेलवर उभे आहात आणि तळाशी उजवीकडे पोहोचण्याची आवश्यकता आहे याचा विचार करा. गंतव्यस्थानावर पोहोचण्यासाठी आपल्याला एकतर खालच्या दिशेने किंवा योग्य दिशेने जाणे आवश्यक आहे. गंतव्यस्थानाने, येथे आपण तळाशी-उजवा सेल आहे एक अट अशी आहे की आपणास अशा मार्गाने पुढे जाणे आवश्यक आहे जे आम्हाला कमाल सरासरी मूल्य देते.

उदाहरण

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

स्पष्टीकरण

जास्तीत जास्त सरासरी मूल्यासह पथ

आम्ही वरच्या-डाव्या सेल वरुन पुढील पध्दतीने खाली आलो आहोत: १-> १०-> १-> १००-> १. म्हणून हे जोडल्यास आपल्याला एकूण ११1 मिळते. सरासरी ११ 10/1 = २२..100 च्या बरोबरीची बनते.

दृष्टीकोन

एखादी जबरदस्त शक्ती पध्दत येऊ शकते, जी तळाशी-उजवीकडील पेशीपर्यंत पोहोचण्यासाठी सर्व संभाव्य मार्ग तयार करते. एकदा आपण सर्व मार्ग व्युत्पन्न केले. आता त्यांच्याकडे जा आणि पथ्यावर पडलेल्या पूर्णांकांची बेरीज शोधा. तर एकदा आपल्याकडे सर्व रकमेची रक्कम असेल. यापैकी जास्तीत जास्त बेरीज शोधा.

परंतु हा दृष्टिकोन वापरल्याने टीएलईमध्ये जाण्याची खात्री आहे किंवा ही मर्यादा ओलांडेल. कारण अशा मार्गांच्या निर्मितीमुळे घनिष्ठ वेळेची गुंतागुंत होईल. तर, वेळेच्या अडचणींनुसार समस्या सोडविण्यासाठी. आम्हाला एक कार्यक्षम तोडगा काढणे आवश्यक आहे. पण, आम्ही ते कसे करू शकतो? हे आपण डायनॅमिक प्रोग्रामिंग वापरून करू शकतो. आणि समस्या देखील मॅक्सिमम पाथ सम समस्येशी खूप साम्य आहे. त्या समस्येमध्ये, आम्हाला 2 डी अ‍ॅरेमध्ये जास्तीत जास्त पथ बेरीज शोधण्याची आवश्यकता आहे. आपण हेच करणार आहोत, परंतु शेवटी, आम्ही सरासरी घेऊ.

म्हणून डायनॅमिक प्रोग्रामिंग दृष्टीकोन आम्ही एक 2 डी डीपी अ‍ॅरे तयार करू जिथे डीपी मॅट्रिक मधील प्रत्येक सेल जास्तीत जास्त बेरीज दर्शवेल जो आपल्याला वरच्या डाव्या कोप from्यातून चालू सेलकडे जाण्याची आवश्यकता असल्यास प्राप्त केली जाऊ शकते. तर आम्ही सामान्य पुनरावृत्ती संबंध लिहू शकतो.

// बेस केसेस
डीपी [०] [०] = अ [०] [०]
डीपी [i] [०] = डीपी [आय -१] [०] + अ [मी] [०] // येथे मी प्रथम पंक्तीपासून मॅट्रिक्सच्या शेवटच्या पंक्तीपर्यंत सुरू होतो
डीपी [०] [मी] = डीपी [०] [आय -१] + अ [०] [मी] // येथे मी प्रथम स्तंभ पासून मॅट्रिक्सच्या शेवटच्या स्तंभापर्यंत प्रारंभ होतो
// पुनरावृत्ती संबंध
डीपी [i] [जे] = जास्तीत जास्त (डीपी [आय -१] [जे], डीपी [i] [जे -१]) + अ [i] [जे] // इतर सर्व पेशींसाठी

जास्तीत जास्त सरासरी मूल्यासह पाथ साठी सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन ^ 2) आम्ही इनपुट अ‍ॅरे वर सहजपणे फिरलो आहोत. आणि आमच्या डीपीमधील संक्रमणास केवळ ओ (1) वेळ लागला.

स्पेस कॉम्प्लेक्सिटी

ओ (एन ^ 2) आम्ही 2D डीपी अ‍ॅरे तयार केल्यापासून.