Шлях з максімальным сярэднім значэннем


Узровень складанасці Лёгка
Часта пытаюцца ў Cisco Эпічныя сістэмы Шэры Аранжавы Лабараторыі SAP Times Інтэрнэт
масіў Дынамічнае праграмаванне матрыца

Пастаноўка праблемы

Праблема "Шлях з максімальным сярэднім значэннем" абвяшчае, што вам даецца 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 альбо перавысіць абмежаванне па часе. Паколькі генерацыя такіх шляхоў прывядзе да экспанентнай складанасці ў часе. Такім чынам, для вырашэння праблемы ва ўмовах часу. Нам трэба знайсці эфектыўнае рашэнне. Але як мы можам гэта зрабіць? Мы можам зрабіць гэта з дапамогай дынамічнага праграмавання. І праблема таксама вельмі нагадвае праблему максімальнай сумы шляху. У гэтай задачы нам трэба знайсці максімальную суму шляху ў 2D-масіве. Тое ж самае мы і будзем рабіць, але ў рэшце рэшт, мы возьмем сярэдняе.

Такім чынам, для Дынамічнае праграмаванне падыход. Мы створым 2D масіў DP, дзе кожная вочка ў матрыцы DP будзе пазначаць максімальную суму, якую можна дасягнуць, калі нам трэба пачаць з левага верхняга кута да бягучай ячэйкі. Такім чынам, мы можам напісаць агульнае суадносіны рэцыдываў.

// Базавыя справы
dp [0] [0] = a [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // тут i пачынаецца з 1-га радка да апошняга радка матрыцы
dp [0] [i] = dp [0] [i-1] + a [0] [i] // тут 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) бо мы проста прайшлі па масіве ўводу. І пераход у нашым ДП заняў толькі O (1) час.

Касмічная складанасць

O (N ^ 2) бо мы стварылі масіў 2D DP.