ሁለት ተሻጋሪዎችን በመጠቀም በፍርግርግ ውስጥ ከፍተኛ ነጥቦችን ይሰብስቡ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን Fab ጎልድማን ሳክስ google Honeywell LinkedIn Pinterest ያሁ
ሰልፍ ተለዋዋጭ ፕሮግራም ማትሪክስ

የችግሩ መግለጫ

እኛ “nxm” የሚል መጠን ያለው ማትሪክስ ተሰጥቶናል ፣ እና ሐሁለት ተሻጋሪዎችን በመጠቀም በፍርግርግ ውስጥ ከፍተኛ ነጥቦችን ይምረጡ ፡፡ በሴል i ላይ የምንቆም ከሆነ ፣ j ከዚያ ወደ ሴል i + 1 ፣ j ወይም i + 1 ፣ j-1or i + 1 ፣ j + 1 ለመሄድ ሦስት አማራጮች አሉን ፡፡ ያ ማለት አሁን ካለው ህዋስ ወደ ታች አቅጣጫ ወደ ቀጣዩ ረድፍ እና ወደ አሁኑ አምድ ወይም ወደ ተጎራባች አምዶች እንሸጋገራለን ፡፡ ከላይኛው ግራ ጥግ ጀምረን ወደ ግራ ታችኛው ጥግ መሄድ ያስፈልገናል ፡፡ ለሁለተኛው መሻገሪያ ከላይኛው ቀኝ ጥግ ወደ ታችኛው ቀኝ ጥግ መሄድ ያስፈልገናል ፡፡

ለምሳሌ

Size of matrix = 3 x 3

Matrix

10 2 20

9 10 5

10 100 20
75

ማብራሪያ-የመጀመሪያ የመተላለፍ እንቅስቃሴዎች ከ10-> 10-> 10 ናቸው ፣ በድምሩ 30 ነጥቦችን ያገኛሉ ፡፡

ሁለተኛው የትራንስፖርት እንቅስቃሴ 20-> 5-> 20 ነው ፣ ስለሆነም አጠቃላይ 20 + 5 + 20 = 45 ነጥቦች ነው። እዚህ ከዚያን ጊዜ ጀምሮ 100 መምረጥ አልቻልንም በሁለቱም ጉዳዮች (የመጀመሪያ እና ሁለተኛ ማቋረጫ) መድረሻችንን መድረስ ባልቻልን ነበር ፡፡ ስለዚህ መሰብሰብ የምንችልባቸው ከፍተኛ ነጥቦች 75 ናቸው ፡፡

ሁለት ተሻጋሪዎችን በመጠቀም በፍርግርግ ውስጥ ከፍተኛ ነጥቦችን ለመሰብሰብ አልጎሪዝም

የዋህ አቀራረብ

እኛ መጠቀም እንችላለን ተደጋጋሚ አቀራረብ ፣ በመጀመሪያ የመጀመሪያውን መሻገሪያ በመጠቀም የሚሰበሰቡትን ከፍተኛ ነጥቦችን የምናገኝበት ፡፡ በመጀመሪያ መሻገሪያ ወቅት ለመጀመሪያው መሻገሪያ እንደ ዱካ ያገለገሉትን ሕዋሶች ምልክት ማድረግ አለብን ፡፡ አሁን የቀኝ ታችኛው ጥግ የሆነውን ሁለተኛ መድረሻችንን ስንደርስ ፡፡ አጠቃላይ ድምርውን አግኝተን መልሱን በዚሁ መሠረት እናዘምነዋለን ፡፡ ስለዚህ ይህንን በማድረጋችን የመጀመሪያ እና የሁለተኛ መተላለፍ ሊሆኑ የሚችሉ ውህደቶችን ሁሉ ባለፍን ነበር ፡፡ ግን ይህ መፍትሔ የግዜ ብዛት ውስብስብነት ስላለው ፣ ተስማሚ አይደለም ፡፡

ውጤታማ አቀራረብ

አንደኛ እና ሁለተኛ ተሻጋሪዎችን በተመሳሳይ ጊዜ እናከናውናለን እና እንጠቀማለን ተለዋዋጭ ፕሮግራም. ስለዚህ ፣ ከላይ ግራ እና ከላይ ከቀኝ ማዕዘኖች እንጀምራለን ፡፡ እና ወደ ታች አቅጣጫ ወደ ቀጣዩ ረድፍ መጓዙን ይቀጥሉ። አሁን ግን በተመሳሳይ ጊዜ እኛ አሻራዎችን ስለምናከናውን ፡፡ እኛ የምንመርጠው በድምሩ 9 ጥምረት አለን (3 ለመጀመሪያው መሻገሪያ እና 3 ለሁለተኛው መሻገሪያ ፣ 3 * 3 = 9 ጥምረት ያደርገዋል) ፡፡

አሁን ንዑስ ፕሮብሌቶች ተደራራቢ ስለሆኑ (ያንን ተመሳሳይ ንዑስ ችግር ብዙ ጊዜ እንፈታዋለን ማለት ነው) ፡፡ ስለሆነም የብዙ ጊዜያችንን ውስብስብነት ወደ ፖሊመሚል የጊዜ ውስብስብነት የሚቀንሱ ንዑስ ፕሮብሌሞችን ውጤት ማከማቸት ይመከራል ፡፡

ኮድ

ሲ ++ ኮድ ሁለት ተሻጋሪዎችን ችግር በመጠቀም በፍርግርግ ውስጥ ከፍተኛ ነጥቦችን ለመሰብሰብ

#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

የጃቫ ኮድ ሁለት ተሻጋሪዎችን ችግር በመጠቀም በፍርግርግ ውስጥ ከፍተኛ ነጥቦችን ለመሰብሰብ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (NM ^ 2) ፣ ጠቅላላ N * M ^ 2 ግዛቶች ስላሉ እና ከፍተኛ ከሆነ ደግሞ ሁሉንም ግዛቶች መጓዝ እንችላለን ፡፡ ለዚህ ስልተ-ቀመር የብዙ-ጊዜ ውስብስብነት አለን።

የቦታ ውስብስብነት

ኦ (NM ^ 2) ፣ ጠቅላላ N * M ^ 2 ግዛቶች ስላሉ እና ከፍተኛ ከሆነ ደግሞ ሁሉንም ግዛቶች መጓዝ እንችላለን ፡፡ እዚህ የዲፒ ድርድር መጠን 3 x ልኬቶች N x M x M አለው ፣ ስለሆነም ባለብዙ ቦታ ጠፈር ውስብስብነት ተገኝቷል።