მაქსიმალური საშუალო მნიშვნელობის გზა


Რთული ტური Easy
ხშირად ეკითხებიან Cisco ეპიკური სისტემები რუხი ნარინჯისფერი SAP ლაბორატორიები Times ინტერნეტი
Array დინამიური პროგრამირება Matrix

პრობლემის განცხადება

პრობლემა "გზა მაქსიმალური საშუალო მნიშვნელობით" აცხადებს, რომ გეძლევათ 2D მასივი ან მთელი რიცხვების მატრიცა. ახლა გაითვალისწინეთ, რომ თქვენ ზედა მარცხენა უჯრედთან დგახართ და უნდა მიაღწიოთ ქვედა მარჯვნივ. დანიშნულების ადგილზე მისასვლელად, თქვენ უნდა გადაადგილდეთ გასწვრივ ან ქვედა მიმართულებით ან სწორი მიმართულებით. დანიშნულების ადგილის მიხედვით, აქ ვგულისხმობთ ქვედა მარჯვენა უჯრედს. არსებობს ერთი პირობა, რომ თქვენ უნდა იმოძრაოთ ისეთ ბილიკზე, რომელიც გვაძლევს მაქსიმალურ საშუალო მნიშვნელობას.

მაგალითი

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 ან გადააჭარბებს ვადას. რადგან ასეთი ბილიკების წარმოქმნა გამოიწვევს ექსპონენციალურ დროის სირთულეს. ასე რომ, პრობლემის გადაჭრა დროში არსებულ შეზღუდვებში. ჩვენ უნდა ვიპოვოთ ეფექტური გამოსავალი. როგორ შეგვიძლია ამის გაკეთება? ეს შეგვიძლია გავაკეთოთ დინამიური პროგრამირების გამოყენებით. პრობლემა ასევე ძალიან ჰგავს Maximum Path Sum პრობლემას. ამ პრობლემაში, ჩვენ უნდა ვიპოვოთ მაქსიმალური ბილიკის ჯამი 2D მასივში. იგივე არის ის, რისი გაკეთებასაც ვაპირებთ, მაგრამ საბოლოოდ, ჩვენ საშუალო მაჩვენებელს ავიღებთ.

ასე რომ დინამიური პროგრამირება მიდგომა. ჩვენ შევქმნით 2D DP მასივს, სადაც თითოეული უჯრედი DP მატრიცაში აღნიშნავს მაქსიმალურ ჯამს, რომლის მიღწევაც შეიძლება, თუ ზედა მარცხენა კუთხიდან უნდა დავიწყოთ ამჟამინდელი უჯრედი. ასე რომ, შეგვიძლია დავწეროთ ზოგადი რეციდივის მიმართება.

// ბაზის შემთხვევები
dp [0] [0] = a [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // აქ მე იწყება 1 რიგიდან მატრიცის ბოლო მწკრივამდე
dp [0] [i] = dp [0] [i-1] + a [0] [i] // აქ მე იწყება 1 სვეტიდან მატრიცის ბოლო სვეტამდე
// განმეორებადი კავშირი
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- ის კოდი Path- ისთვის, საშუალო მაქსიმალური მნიშვნელობით

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) მას შემდეგ რაც შევქმენით 2D DP მასივი.