Проблем рудника злата


Ниво тешкоће Средњи
Често питани у амазонка Флипкарт гоогле мицрософт ПаиУ Убер
Ред Динамичко програмирање матрица

Изјава о проблему

„Проблем рудника злата“ наводи да сте добили 2Д решетка имајући неке негативне новчиће смештене у сваку ћелију дате мреже. У почетку рудар стоји на првој колони, али у реду нема ограничења. Може да започне у било ком реду. Рудар се може кретати само у правом смеру до следеће наредне колоне. Такође се може кретати дијагоналама. Дакле, из сваке ћелије имате три правца, десно, горе десно или доле десно. Али ћелија би требала бити унутар граница мреже. Морате да утврдите која је максимална количина златника коју он може прикупити?

matrix = {{10, 20, 0},
          {30, 10, 100},
          {10, 10, 10}}
The maximum coins he can collect = 150

Објашњење: Погледајте слику за путању, рудар би требало да одабере за прикупљање 150 златника.

Проблем рудника злата

Приступ за проблем рудника злата

Наиван приступ може бити коришћење повратног праћења да би се произвеле све путање које рудар може да пређе од прве до последње колоне. И за сваку путању израчунајте број златника прикупљених на свакој путањи. Али овај приступ је дуготрајан и премашиће временско ограничење како повећавамо величину мреже.

Бољи приступ биће коришћење неких нама познатих чињеница. Знамо да рудар може доћи до тренутне ћелије само из три ћелије, ћелије која се налази лево од тренутне ћелије, ћелије која се налази одмах изнад ове леве ћелије и ћелије која се налази на дну ове леве ћелије. Дакле, можемо узети максимум од ове три вредности, даће нам максимум кованица које можемо прикупити ако смо у тренутној ћелији. Дакле, користићемо динамичко програмирање за чување резултата за било коју тренутну ћелију. То је максималан број новчића који се могу прикупити ако рудар дође у тренутну ћелију.

код

Ц ++ код за проблем Голд Мине

#include<bits/stdc++.h> 
using namespace std; 


int main()
{
    // grid size n*m
    int n,m;cin>>n>>m;
    int a[n][m]; // grid storing the number of gold coins in each cell
    // taking input of the grid storing the number of gold coins
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    }

    /*
    
    ^  ^  ^
     \
    ^- &  ^
     /
    ^  ^  ^
    Consider this represents a grid and we are currently at a cell having & stored in it.
    So only there are three cells from which miner could have reached current cell
    So we take maximum of all the options and thus at the end in the last corner
    We receive the largest amount of gold coins.
    */
    for(int j=1;j<m;j++){
        for(int i=0;i<n;i++)
            a[i][j] += max({((i>0) ? a[i-1][j-1] : 0), a[i][j-1], ((i+1<n) ? a[i+1][j-1] : 0)});
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        ans = max(ans, a[i][m-1]);
    }
    cout<<ans<<endl;
}
3 3
10 20 0
30 10 100
10 10 10
150

Јава код за проблем Голд Мине

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// grid size n*m
    	int m = sc.nextInt();
      int a[][] = new int[n][m]; // grid storing the number of gold coins in each cell
      // taking input of the grid storing the number of gold coins
      for(int i=0;i<n;i++){
          for(int j=0;j<m;j++)
              a[i][j] = sc.nextInt();
      }

      /*
      
      ^  ^  ^
       \
      ^- &  ^
       /
      ^  ^  ^
      Consider this represents a grid and we are currently at a cell having & stored in it.
      So only there are three cells from which miner could have reached current cell
      So we take maximum of all the options and thus at the end in the last corner
      We receive the largest amount of gold coins.
      */
      for(int j=1;j<m;j++){
          for(int i=0;i<n;i++){
          	int topLeft = ((i>0) ? a[i-1][j-1] : 0);
          	int justLeft = a[i][j-1];
          	int bottomLeft = ((i+1<n) ? a[i+1][j-1] : 0);
              int maxOfAll = Math.max(topLeft, bottomLeft);
              maxOfAll = Math.max(maxOfAll, justLeft);
              a[i][j] += maxOfAll;
          }
      }

      int ans = 0;
      for(int i=0;i<n;i++){
          ans = Math.max(ans, a[i][m-1]);
      }
    System.out.println(ans);
  }
}
3 3
10 20 0
30 10 100
10 10 10
150

Анализа сложености

Сложеност времена

НА М), јер смо морали да пређемо кроз целу мрежу. А пошто има Н * М ћелије. Сложеност времена је полиномна.

Сложеност простора

О (1), пошто смо користили почетну матрицу за рад. Нисмо користили никакву додатну матрицу / мрежу за чување средњих резултата. Али програм у целини захтева сложеност простора О (Н * М).