સોનાની ખાણની સમસ્યા


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફ્લિપકાર્ટ Google માઈક્રોસોફ્ટ પે ઉબેર
અરે ડાયનેમિક પ્રોગ્રામિંગ મેટ્રિક્સ

સમસ્યા નિવેદન

“ગોલ્ડ માઇન પ્રોબ્લેમ” જણાવે છે કે તમને 2 ડી આપવામાં આવે છે ગ્રિડ આપેલ ગ્રીડના દરેક કોષમાં કેટલાક બિન-નકારાત્મક સિક્કાઓ રાખેલ છે. શરૂઆતમાં, ખાણિયો પ્રથમ ક columnલમ પર isભો છે પરંતુ પંક્તિ પર કોઈ પ્રતિબંધ નથી. તે કોઈપણ પંક્તિથી શરૂ કરી શકે છે. ખાણિયો ફક્ત આગળની ક columnલમ પર માત્ર યોગ્ય દિશામાં જઇ શકે છે. તે કર્ણોમાં પણ આગળ વધી શકે છે. તેથી દરેક કોષમાંથી, તમારી પાસે ત્રણ દિશાઓ છે, ફક્ત જમણી તરફ, ઉપર જમણે અથવા નીચે જમણે. પરંતુ કોષ ગ્રીડની સીમાની અંદર હોવો જોઈએ. તમારે તે શોધવાની જરૂર છે કે તે સોનાના સિક્કાની મહત્તમ રકમ શું એકત્રિત કરી શકે છે?

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

સમજૂતી: માર્ગ માટેની છબી જુઓ, ખાણિયોએ 150 સોનાના સિક્કા એકત્રિત કરવા માટે પસંદ કરવી જોઈએ.

સોનાની ખાણની સમસ્યા

સોનાની ખાણ સમસ્યા માટે અભિગમ

એક નિષ્કપટ અભિગમ એ ખાણકામ કરનાર પ્રથમ ક columnલમથી છેલ્લી ક takeલમ સુધી લઈ શકે છે તે તમામ પાથોના નિર્માણ માટે બેકટ્રેકિંગનો ઉપયોગ કરી શકાય છે. અને દરેક પાથ માટે દરેક પાથ પર એકત્રિત થયેલ સોનાના સિક્કાની સંખ્યાની ગણતરી કરો. પરંતુ આ અભિગમ સમય માંગી લે તેવો છે અને આપણે ગ્રીડનું કદ વધારતાં સમય મર્યાદાથી વધુ થઈ જશે.

વધુ સારી અભિગમ એ અમુક તથ્યોનો ઉપયોગ કરવાનો છે જે આપણને જાણીતા છે. આપણે જાણીએ છીએ કે ખાણિયો વર્તમાન કોષમાં ફક્ત ત્રણ કોષોથી જ આવી શકે છે, તે કોષ જે વર્તમાન કોષની ડાબી બાજુ છે, તે કોષ જે આ ડાબા કોષની ઉપર છે, અને કોષ જે ફક્ત આ ડાબા કોષની નીચે છે. તેથી આપણે આ ત્રણ કિંમતોમાંથી મહત્તમ લઈ શકીએ તો આપણને મહત્તમ સિક્કા મળશે જે આપણે વર્તમાન કોષમાં હોઈએ તો એકત્રિત કરી શકાય. તેથી, આપણે તેનો ઉપયોગ કરીશું ગતિશીલ પ્રોગ્રામિંગ કોઈપણ વર્તમાન સેલ માટે પરિણામ સંગ્રહવા માટે. જો ખાણિયો વર્તમાન કોષમાં આવે તો તે મહત્તમ સિક્કાની સંખ્યા છે.

કોડ

ગોલ્ડ માઇન સમસ્યા માટે સી ++ કોડ

#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), કારણ કે આપણે પ્રારંભિક મેટ્રિક્સનો ઉપયોગ કરવા માટે કર્યું છે. અમે મધ્યવર્તી પરિણામો સંગ્રહિત કરવા માટે કોઈપણ વધારાના મેટ્રિક્સ / ગ્રીડનો ઉપયોગ કર્યો નથી. પરંતુ સંપૂર્ણ પ્રોગ્રામને ઓ (એન * એમ) જગ્યા જટિલતાની જરૂર છે.