Java-maksymalna suma w ścieżce przez tablicę 2D

Question

Java-maksymalna suma w ścieżce przez tablicę 2D

Zasadniczo mam problem, który idzie coś podobnego do tego:

Jest ogród z roślin truskawek reprezentowany przez 2D, kwadratowy układ. Każda roślina (każdy element) ma liczbę truskawek. Zaczynasz od lewego górnego rogu tablicy i możesz poruszać się tylko w prawo lub w dół. Muszę zaprojektować rekurencyjną metodę obliczania ścieżek przez ogród, a następnie określić, która z nich daje najwięcej truskawek.

Myślę, że rozumiem naprawdę naprawdę proste problemy z rekurencją, ale ten problem przerosł moją głowę. Nie jestem pewien, od czego zacząć, ani dokąd pójść, jeśli chodzi o tworzenie metody rekurencyjnej.

Każda pomoc związana z kodem lub pomoc w zrozumieniu koncepcji stojącej za tym problemem jest bardzo mile widziana. Dzięki.

9

java arrays path 2d sum

Author: user1547050, 2012-07-24

Source

3 answers

Możesz to zrobić używając memoizacji. Oto Pseudodoce Javy(memo, R, i C są zakładane jako zmienne instancji dostępne dla metody max).

int R = 10, C = 20;
int memo[][] = new int[R][C];
for (int r=0 ; r != R ; r++)
    for (int c = 0 ; c != C ; c++)
        memo[r][c] = -1;
int res = max(0, 0, field);

int max(int r, int c, int[][] field) {
    if (memo[r][c] != -1) return memo[r][c];
    int down = 0; right = 0;
    if (r != R) down = max(r+1, c, field);
    if (c != C) right = max(r, c+1, field);
    return memo[r][c] = (field[r][c] + Math.max(down, right));
}

4

Author: dasblinkenlight,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-07-23 22:21:15

Można to rozwiązać za pomocą metody tabulacji DP, dzięki której można zaoszczędzić miejsce od O(m*n) do tylko O(N). W przypadku zapamiętywania DP potrzebna jest matryca m * n do przechowywania wartości pośrednich. Poniżej znajduje się mój kod Pythona. Mam nadzieję, że to pomoże.

def max_path(field):
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)]
    for i in range(1, len(field)):
        for j in range(len(dp)):
            dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j]
    return dp[-1]

0

Author: Jonathon.lau,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-02-15 22:37:15

score 14 · Accepted Answer

Jak powiedział dasblinkenlight, najskuteczniejszym sposobem na to jest użycie memoizacji lub dynamicznej techniki programowania. Preferuję programowanie dynamiczne, ale użyję tu czystej rekurencji.

Odpowiedź skupia się wokół odpowiedzi na jedno fundamentalne pytanie: "jeśli jestem w kwadracie w rzędzie r i kolumnie c na moim polu, Jak mogę ocenić ścieżkę od lewego górnego rogu do tego miejsca, tak aby zmaksymalizować liczbę truskawek?"

Kluczem do zrozumienia jest to, że są tylko dwa sposoby aby dostać się do działki w wierszu r i kolumnie c: albo mogę dostać się tam z góry, używając działki w wierszu r - 1 i kolumnie c, albo mogę dostać się tam z boku, używając działki w wierszu r i kolumny c-1. Potem musisz się tylko upewnić, że znasz swoje podstawowe sprawy...co oznacza, zasadniczo, moja czysto rekurencyjna wersja byłaby czymś w stylu:

int[][] field;    
int max(int r, int c) {
    //Base case
    if (r == 0 && c == 0) {
        return field[r][c];
    }
    //Assuming a positive number of strawberries in each plot, otherwise this needs
    //to be negative infinity
    int maxTop = -1, maxLeft = -1;
    //We can't come from the top if we're in the top row
    if (r != 0) {
        maxTop = field[r-1][c];
    }
    //Similarly, we can't come from the left if we're in the left column
    if (c != 0) {
        maxLeft = field[r][c-1];
    }
    //Take whichever gives you more and return..
    return Math.max(maxTop, maxLeft) + field[r][c];
}

Zadzwoń do Maxa (r-1, c-1), Aby uzyskać odpowiedź. Zauważ, że jest tu dużo nieefektywności; zrobisz znacznie lepiej używając programowania dynamicznego (który Podam poniżej) lub memoizacja (która została już zdefiniowana). Należy jednak pamiętać, że zarówno techniki DP, jak i memoizacji są po prostu bardziej wydajnymi sposobami, które wynikają z użytych tutaj reguł rekurencyjnych.

DP:

int maxValue(int[][] field) {
    int r = field.length;
    int c = field[0].length;
    int[][] maxValues = new int[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (i == 0 && j == 0) {
                maxValues[i][j] = field[i][j];
            } else if (i == 0) {
                maxValues[i][j] = maxValues[i][j-1] + field[i][j];
            } else if (j == 0) {
                maxValues[i][j] = maxValues[i-1][j] + field[i][j];
            } else {
                maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j];
            }
        }
    }
    return maxValues[r-1][c-1];
}

W obu przypadkach, jeśli chcesz odtworzyć ścieżkę, po prostu zachowaj tabelę logiczną 2D, która odpowiada "czy przyszedłem z góry czy z lewej"? Jeśli najbardziej truskawkowa ścieżka pochodzi z góry, umieść true, w przeciwnym razie umieść false. Że może pozwolić na ponowne prześledzenie poprawki po obliczeniach.

Zauważ, że nadal jest to rekurencyjne w zasadzie: na każdym kroku patrzymy wstecz na nasze poprzednie wyniki. Tak się składa, że buforujemy nasze poprzednie wyniki, więc nie marnujemy grosza pracy i atakujemy podproblemy w inteligentnej kolejności, abyśmy zawsze mogli je rozwiązać. Więcej informacji na temat programowania dynamicznego można znaleźć w Wikipedia.