Problema con il problema Project Euler 18

Question

Attualmente sto cercando di risolvere problem 18 of project Euler. L'obiettivo è:

Iniziando nella parte superiore del triangolo sotto e trasferirsi numeri adiacenti sulla riga in basso, la massima totale da cima a fondo è 23.

 
     3 
    7 4 
    2 4 6 
    8 5 9 3 

Cioè, 3 + 7 + 4 + 9 = 23.

Trovare il massimo totale da cima a fondo del triangolo di seguito:

 
       75 
       95 64 
       17 47 82 
       18 35 87 10 
      20 04 82 47 65 
      19 01 23 75 03 34 
      88 02 77 73 07 63 67 
      99 65 04 28 06 16 70 92 
     41 41 26 56 83 40 80 70 33 
     41 48 72 33 47 32 37 16 94 29 
     53 71 44 65 25 43 91 52 97 51 14 
     70 11 33 28 77 73 17 78 39 68 17 57 
    91 71 52 38 17 14 91 43 58 50 27 29 48 
    63 66 04 68 89 53 67 30 73 16 69 87 40 31 
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 

ho cercato di risolvere con il seguente algoritmo:

public static void main(String[] args) throws NumberFormatException, IOException { 

     int[][] values = readFile(); 
     int depth = values.length - 2; 

     while (depth >= 0) { 
      for (int j = 0; j < depth; j++) { 
       values[depth][j] += Math.max(values[depth+1][j], values[depth+1][j+1]); 
      } 
      depth += -1; 
     } 

     values[0][0] += Math.max(values[1][0], values[1][1]); 

      System.out.println("The maximum path sum is: " + values[0][0]); 
    } 

I valori di matrice contiene tutti i numeri dal triangolo dove values[0][0] è l'elemento nella riga superiore e values[n][n] è l'ultimo elemento nell'ultima riga.

L'algoritmo utilizza l'approccio che se per esempio inizio nell'ultima riga e ho la scelta tra 04 + 63 e 62 + 63, la somma del campo in cui 63 è stata impostata su 125 perché questa è la importo più alto Questo algoritmo funziona per il piccolo triangolo, ma per il grande triangolo sembra fallire. Non sono sicuro del perché e apprezzerei ogni suggerimento.

Answer 1

Credo che la linea:

for (int j = 0; j < depth; j++) { 

dovrebbe essere

for (int j = 0; j <= depth; j++) { 

perché in questo momento non si sta visitando l'ultimo elemento su ogni riga. Certo, quindi non è necessario la linea

values[0][0] += Math.max(values[1][0], values[1][1]); 

perché è già fatto nel ciclo.

Answer 2

Questa potrebbe non essere la soluzione migliore, ma cosa succede se per ogni iterazione si tiene traccia della somma fino a quel punto. Quindi quando vai all'ultima riga il valore massimo sarebbe la tua risposta.

Answer 3

Non conosco l'algoritmo corretto, ma c'è una semplice dimostrazione del commento di @Johns sulla domanda, che la migliore scelta locale non porta necessariamente alla migliore soluzione globale.

considerare questo (estrema) Esempio:

 
    1 
    1 0 
    1 0 1000 
1 0 0 0 
1 0 0 0 0 

Dato l'algoritmo, si sarebbe ovviamente scendere la stessa sinistra del percorso e mai letto 1000 che deve essere sulla strada migliore.