İki keçiddən istifadə edərək bir şəbəkədə maksimum xal toplayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Fab Goldman Sachs google Honeywell LinkedIn Pinterest Yahoo
Geyim Dinamik proqramlaşdırma MatrisBaxılıb 37

Problem bəyanat

Bizə “nxm” ölçülü bir matris verilir və c-ə ehtiyacımız variki keçiddən istifadə edərək bir şəbəkədəki maksimum nöqtələri silin. Əgər biz i, j hücrəsində dayanırıqsa, onda i + 1, j və ya i + 1, j-1 və ya i + 1, j + 1 hüceyrəsinə getmək üçün üç seçimimiz var. Yəni cari hücrədən aşağı istiqamətdə növbəti sıraya və cari sütuna və ya bitişik sütunlara keçəcəyik. Sol üst küncdən başlayıb sol alt küncə getməliyik. İkinci keçid üçün sağ üst küncdən sağ alt küncə keçməliyik.

misal

Pin

Size of matrix = 3 x 3

Matrix

10 2 20

9 10 5

10 100 20
75

İzahat: İlk keçid hərəkətləri 10-> 10-> 10 arasındadır və cəmi 30 xal qazanır.

İkinci keçid hərəkətləri 20-> 5-> 20, nəticədə cəmi 20 + 5 + 20 = 45 baldır. Burada o vaxtdan bəri 100-ü seçə bilmədik, hər iki halda da təyinatımıza çata bilməyəcəyik (Birinci və ikinci keçid). Beləliklə topladığımız maksimum bal 75-dir.

İki keçiddən istifadə edərək bir şəbəkədə maksimum xal toplamaq üçün alqoritm

Sadəlövh yanaşma

İstifadə edə bilərik rekursiv əvvəlcə ilk keçiddən istifadə edərək toplanacaq maksimum nöqtələri tapdığımız yanaşma. İlk keçid zamanı ilk keçid üçün yol kimi istifadə olunan hüceyrələri qeyd etməliydik. İndi ikinci hədəfimizə çatanda sağ alt küncdür. Ümumi cəmi tapırıq və cavabı müvafiq olaraq yeniləyirik. Beləliklə, bunu etməklə birinci və ikinci keçidin mümkün olan bütün birləşmələrindən keçmiş olardıq. Ancaq bu həll eksponent zaman mürəkkəbliyinə malik olduğundan uyğun deyil.

Səmərəli yanaşma

Birinci və ikinci keçidləri eyni vaxtda aparırıq və istifadə edirik dinamik proqramlaşdırma. Beləliklə, yuxarı sol və yuxarı sağ künclərdən başlayacağıq. Və aşağı istiqamətdə növbəti sıraya keçməyə davam edin. Ancaq indi eyni zamanda traversal çalıştırdığımız üçün. Seçmək üçün cəmi 9 kombinasiyamız var (birinci keçid üçün 3, ikinci keçid üçün 3, bunu 3 * 3 = 9 kombinasiya halına gətiririk).

İndi alt problemlər üst-üstə düşdüyü üçün (yəni eyni alt problemi dəfələrlə həll edəcəyik). Beləliklə, eksponent zaman mürəkkəbliyimizi polinom zaman mürəkkəbliyinə endirəcək alt problemlərin nəticəsini saxlamaq məsləhətdir.

Kodu

C ++ kodu iki keçid problemindən istifadə edərək bir şəbəkədə maksimum xal toplamaq üçün

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

int dir[3] = {-1, 0, 1};
bool isValid(int x, int y1, int y2, int rowSize, int colSize){
    return (x>=0 && x<rowSize && y1>=0 && y1<colSize && y2>=0 && y2<colSize);
}

int collectMaxPointsInGridUsingTwoTraversals(vector<vector<int>> &matrix, vector<vector<vector<int>>> &dp, int x, int y1, int y2, int rowSize, int colSize)
{
    if(!isValid(x, y1, y2, rowSize, colSize))
        return INT_MIN;
    if (x == rowSize-1 && y1 == 0 && y2 == colSize-1)
        return (y1 == y2)? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
    if (x == rowSize-1)
        return INT_MIN;

    if (dp[x][y1][y2] != -1)
        return dp[x][y1][y2];

    int ans = INT_MIN;
    int currentVal = (y1 == y2) ? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);

    for(int i = 0; i < 3; i++){
        for(int j=0;j<3;j++){
            ans = max(ans, currentVal + collectMaxPointsInGridUsingTwoTraversals(matrix, dp, x+1, y1+dir[i], y2+dir[j], rowSize, colSize));
        }
    }
    return (dp[x][y1][y2] = ans);
}

int main()
{
    int rowSize, colSize;
    cin>>rowSize>>colSize;
    vector<vector<int>> matrix(rowSize, vector<int>(colSize));
    vector<vector<vector<int>>> dp(rowSize, vector<vector<int>>(colSize, vector<int>(colSize, -1)));
    for(int i=0;i<rowSize;i++){
        for(int j=0;j<colSize;j++)
            cin>>matrix[i][j];
    }
    cout << "Maximum collection is " <<collectMaxPointsInGridUsingTwoTraversals(matrix, dp, 0,0,colSize-1, rowSize, colSize);
    return 0;
}
3 3
10 1 20
5 10 5
10 100 20
Maximum collection is 75

Java kodu iki keçid problemindən istifadə edərək bir şəbəkədə maksimum xal toplamaq üçün

import java.util.*;

class Main{
    
    static int dir[] = {-1, 0, 1};
    static boolean isValid(int x, int y1, int y2, int rowSize, int colSize){
        return (x>=0 && x<rowSize && y1>=0 && y1<colSize && y2>=0 && y2<colSize);
    }
    
    static int collectMaxPointsInGridUsingTwoTraversals(int[][] matrix, int[][][] dp, int x, int y1, int y2, int rowSize, int colSize)
    {
        if(!isValid(x, y1, y2, rowSize, colSize))
            return Integer.MIN_VALUE;
        if (x == rowSize-1 && y1 == 0 && y2 == colSize-1)
            return (y1 == y2)? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
        if (x == rowSize-1)
            return Integer.MIN_VALUE;
    
        if (dp[x][y1][y2] != -1)
            return dp[x][y1][y2];
    
        int ans = Integer.MIN_VALUE;
        int currentVal = (y1 == y2) ? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
    
        for(int i = 0; i < 3; i++){
            for(int j=0;j<3;j++){
                int tmp = currentVal + collectMaxPointsInGridUsingTwoTraversals(matrix, dp, x+1, y1+dir[i], y2+dir[j], rowSize, colSize);
                ans = Math.max(ans, tmp);
            }
        }
        return (dp[x][y1][y2] = ans);
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int rowSize = sc.nextInt();
        int colSize = sc.nextInt();
        int matrix[][] = new int[rowSize][colSize];
        int dp[][][] = new int[rowSize][colSize][colSize];
        for(int i=0;i<rowSize;i++){
            for(int j=0;j<colSize;j++){
                matrix[i][j] = sc.nextInt();
                for(int k=0;k<colSize;k++)
                    dp[i][j][k] = -1;
            }
        }
        int answer = collectMaxPointsInGridUsingTwoTraversals(matrix, dp, 0,0,colSize-1, rowSize, colSize);
        System.out.println("Maximum collection is "+answer);
    }
}
3 3
10 1 20
5 10 5
10 100 20
Maximum collection is 75

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (NM ^ 2), cəmi N * M ^ 2 vəziyyəti olduğundan və maksimum olaraq bütün vəziyyətləri gəzə bilərik. Bu alqoritm üçün polinom-zaman mürəkkəbliyinə sahibik.

Kosmik Mürəkkəblik

O (NM ^ 2), cəmi N * M ^ 2 vəziyyəti olduğundan və maksimum olaraq bütün vəziyyətləri gəzə bilərik. Burada DP dizisi N x M x M ölçüsündə 3 ölçüyə malikdir, beləliklə polinom boşluğu mürəkkəbliyi əldə edilir.

Translate »