Proyecto Euler 18

Question

Hey, trabaja en el Proyecto de Euler, y éste me está dando algunos problemas

Al comenzar en la parte superior del triángulo de abajo y moviéndose a números adyacentes en la fila de abajo, el volumen total máximo de arriba a abajo es 23.

Es decir, + 7 + 3 + 4 = 9 23.

Encontrar el volumen total máximo de arriba a abajo del triángulo a continuación:

...

NOTA: Como solo hay 16384 rutas, es posible resolver este problema probando cada ruta. Sin embargo, el problema 67 es el mismo desafío con un triángulo que contiene cien filas; ¡no puede ser resuelto por la fuerza bruta, y requiere un método inteligente! ; O)

aquí es el algoritmo que he usado para resolverlo

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Problem18 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      string triangle = @"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"; 
      string[] rows = triangle.Split('\n'); 
      int currindex = 1; 
      int total = int.Parse(rows[0]); 
      Console.WriteLine(rows[0]); 
      for (int i = 1; i < rows.Length; i++) 
      { 
       string[] array1 = rows[i].Split(' '); 
       if (array1.Length > 1) 
       { 
        if (int.Parse(array1[currindex - 1]) > int.Parse(array1[currindex])) 
        { 
         Console.WriteLine(array1[currindex - 1]); 
         total += int.Parse(array1[currindex - 1]); 
        } 
        else 
        { 
         Console.WriteLine(array1[currindex]); 
         total += int.Parse(array1[currindex]); 
         currindex++; 
        } 
       } 
      } 
      Console.WriteLine("Total: " + total); 
      Console.ReadKey(); 
     } 
    } 
} 

ahora cada vez que lo dirige, se trata con 1064, sólo el 10 por menos de la solución - 1074

no he encontrado ningún problema con el algoritmo y lo hice a mano y también se inventó 1064, cualquiera sabe si la solución es incorrecta, interpreto la pregunta incorrectamente, o si solo hay un error en el algoritmo ?

Answer 1

Su problema es que su algoritmo es un algoritmo voraz, siempre encontrando máximos locales. Desafortunadamente, eso hace que pierda números más altos abajo porque están directamente debajo de números más bajos. Por ejemplo, si el triángulo fuera solo 3 niveles, su algoritmo escogería 75 + 95 + 47 = 217, mientras que la respuesta correcta es 75 + 64 + 82 = 221.

El algoritmo correcto probará cada ruta y elegirá el que tiene el total más alto, o calcule los caminos de abajo hacia arriba (lo que le permite evitar probar cada uno, por lo tanto, es mucho más rápido). Debo añadir que trabajar desde abajo hacia arriba no solo es mucho más rápido (O (n^2) en lugar de O (2^n)!), Sino también mucho más fácil de escribir (lo hice en aproximadamente 3 líneas de código) .

Answer 2

Has escrito greedy algorithm, que no creo que cumpla los requisitos aquí. Aquí está un ejemplo rápido para demostrar ese punto:

1 
2 1 
1 1 100 

Uso del algoritmo se llega a una suma de 4, aunque la solución óptima es de 102.

Answer 3

Aquí es una descripción gráfica:

Answer 4

Esto es lo que el método de abajo hacia arriba belisarius describe - usando el triángulo trivial dada en el problema 18 - Parece que, en caso de que la imagen en su puesto es confuso para cualquier otra persona

 03 
    07 04 
    02 04 06 
08 05 09 03 

     03 
    07 04 
    02 04 06 
08 05 09 03 
^^^^^^ 

     03 
    07 04 
    10 04 06 
08 05 09 03 
    ^^^^^^ 

     03 
    07 04 
    10 13 06 
08 05 09 03 
     ^^^^^^ 

     03 
    07 04 
    10 13 15 
    ^^^^^^ 
08 05 09 03 

     03 
    20 04 
    10 13 15 
     ^^^^^^ 
08 05 09 03 

     03 
    20 04 
    10 13 15 
     ^^^^^^ 
08 05 09 03 

     03 
    20 19 
    ^^^^^^ 
    10 13 15 
08 05 09 03 

     23 
     ^^ 
    20 19 
    10 13 15 
08 05 09 03 

Answer 5

Recursive (no necesariamente la mejor) enfoque:

static int q18(){ 
     int matrix[][] = // BIG MATRIX; 
     return getMaxPath(matrix, 0, 0, 0); 
    } 
    static int getMaxPath(int matrix[][], int sum, int row, int col){ 
     if(row==matrix.length) return sum; 
     return Math.max(getMaxPath(matrix, sum+matrix[row][col], row+1, col), 
         getMaxPath(matrix, sum+matrix[row][col], row+1, col+1)); 
    }