ოქროს ნაღმების პრობლემა


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Flipkart Google microsoft პეუ Uber
Array დინამიური პროგრამირება Matrix

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

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

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

განმარტება: იხილეთ სურათის გზა, miner უნდა აირჩიოს შეგროვება 150 ოქროს მონეტა.

ოქროს ნაღმების პრობლემა

მიდგომა ოქროს მაღაროს პრობლემის მიმართ

გულუბრყვილო მიდგომა შეიძლება იყოს backtracking- ის გამოყენება, ყველა იმ ბილიკის წარმოსაქმნელად, რომლებსაც მაღაროელი შეძლებს პირველი სვეტიდან ბოლო სვეტამდე მისვლა. თითოეული ბილიკისთვის გამოთვალეთ თითოეულ ბილიკზე შეგროვებული ოქროს მონეტების რაოდენობა. მაგრამ ეს მიდგომა შრომატევადია და გადააჭარბებს დროის შეზღუდვას, რადგან ქსელის ზომას ვზრდით.

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

კოდი

C ++ კოდი ოქროს ნაღმების პრობლემისთვის

#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

სირთულის ანალიზი

დროის სირთულე

O (N * M), იმის გამო, რომ მთელი ქსელის გავლა მოგვიწია. რადგან მას აქვს N * M უჯრედები. დროის სირთულე მრავალწევრია.

სივრცის სირთულე

O (1), ვინაიდან საწყის მატრიცაზე ვიყენებდით მუშაობას. ჩვენ არ გამოვიყენეთ რაიმე დამატებითი მატრიცა / ქსელი შუალედური შედეგების შესანახად. მთლიანობაში პროგრამა მოითხოვს O (N * M) სივრცის სირთულეს.