अधिकतम औसत मानको साथ पथ  


कठिनाई तह सजिलो
बारम्बार सोधिन्छ सिस्को एपिक सिस्टमहरू ग्रेऑरेंज SAP ल्याबहरू टाइम्स इन्टरनेट
एरे डायनामिक प्रोग्रामिंग म्याट्रिक्स

समस्या वक्तव्य  

समस्या "अधिकतम औसत मानको साथ पथ" भन्छ कि तपाईंलाई २ डी एरे वा म्याट्रिक्स पूर्णा .्क दिइन्छ। अब विचार गर्नुहोस् तपाईं शीर्ष बायाँ सेलमा उभिनुभयो र तल दायाँ पुग्न आवश्यक छ। गन्तव्यमा पुग्नको लागि, तपाईं तल तर्फ वा सही दिशामा पछाडि सर्न आवश्यक छ। गन्तव्य द्वारा, यहाँ हामी तल्लो दायाँ सेल मतलब। एउटा शर्त त्यहाँ छ, कि तपाईं यस्तो पथ को लागी आवश्यक छ जसले हामीलाई अधिकतम औसत मान दिन्छ।

उदाहरणका  

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

स्पष्टीकरण

अधिकतम औसत मानको साथ पथपिन

हामी माथिको बायाँ सेलबाट निम्न तरिकामा सर्‍यौं: १-> १०-> १-> १००-> १ यसैले यसलाई थप्न हामीलाई ११ sum को कुल योग दिन्छ। औसत यसरी ११ 1// = २२..10 बराबर हुन्छ।

दृष्टिकोण  

एक जनावर बल दृष्टिकोणको साथ आउन सक्छ, जुन तल-दायाँ सेलमा पुग्न सबै सम्भावित तरिकाहरू उत्पन्न गर्ने हो। एकचोटि तपाईंले सबै पथहरू उत्पन्न गर्नुभयो। अब तिनीहरूमा जानुहोस् र पथमा लागेका पूर्णांकहरूको योगफल फेला पार्नुहोस्। त्यसो भए, एकचोटि तपाईंसँग सबै योगफलहरू हुन्छन्। यी मध्ये जो अधिकतम हो योगफल खोज्नुहोस्।

तर यो दृष्टिकोण प्रयोग गरेर TLE मा जान निश्चित छ वा समय सीमा नाघ्छ। किनभने त्यस्ता मार्गहरूको उत्पादनले घातीय समयको जटिलताको लागि डोर्‍याउँछ। त्यसो भए, समयको अवरोधमा समस्या समाधान गर्न। हामीले एक दक्ष समाधान खोज्नु पर्छ। तर हामी कसरी त्यसो गर्न सक्छौं? हामी त्यो गतिशील प्रोग्रामिंग प्रयोग गरेर गर्न सक्दछौं। र समस्या पनि अधिक पाथ Sum समस्यासँग धेरै मिल्दोजुल्दो छ। त्यो समस्यामा हामीले २ डी एर्रेमा अधिकतम पथ योग फेला पार्नु पर्छ। उही कुरा के हामी गर्न गइरहेका छौं, तर अन्त्यमा, हामी औसत लिनेछौं।

पनि हेर्नुहोस्
सब भन्दा लामो पुनरावृत्ति

त्यसो भए डायनामिक प्रोग्रामिंग दृष्टिकोण हामी एक २ डी डीपी एर्रे सिर्जना गर्नेछौं जहाँ डीपी मैट्रिकमा प्रत्येक सेलले अधिकतम योगलाई जनाउँछ जुन हामीले प्राप्त गर्न सक्दछ यदि हामीले माथि बायाँ कुनामाबाट हालको सेलमा सुरु गर्नु पर्छ भने। त्यसैले हामी सामान्य पुनरावृत्ति सम्बन्ध लेख्न सक्छौं।

// बेस केसहरू
dp [०] [०] = a [०] [०]
dp [i] [०] = dp [i-0] [०] + a [i] [०] // यहाँ म पहिलो प row्क्तिबाट सुरु हुन्छ मैट्रिक्सको अन्तिम प row्क्ति सम्म
dp [०] [i] = dp [०] [i-0] + a [०] [i] // यहाँ म पहिलो स्तम्भबाट सुरू हुन्छ म्याट्रिक्सको अन्तिम स्तम्भ सम्म
// पुनरावृत्ति सम्बन्ध
dp [i] [j] = अधिकतम (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 ^) किनकि हामी केवल इनपुट एर्रेमा पार गर्दै छौं। र हाम्रो DP मा संक्रमण O (1) समय मात्र लाग्यो।

पनि हेर्नुहोस्
अधिकतम स्ट्याक

ठाउँ जटिलता

O (N ^) किनकि हामीले २d DP एर्रे सिर्जना गरेका छौं।