Project Euler 18

Question

Hey, lavorato a Project Euler, e questo mi sta dando qualche problema

Iniziando nella parte superiore del triangolo sotto e trasferirsi numeri adiacenti sulla riga in basso, il totale massima dall'alto verso il basso è 23.

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

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

...

NOTA: Come ci sono solo 16384 percorsi, è possibile risolvere questo problema provando ogni percorso. Tuttavia, Problema 67, è la stessa sfida con un triangolo contenente cento righe; non può essere risolto con la forza bruta e richiede un metodo intelligente! ; O)

ecco l'algoritmo che ho usato per risolverlo

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(); 
     } 
    } 
} 

Ora ogni volta che eseguo, si tratta con 1064, solo 10 in meno allora la soluzione - 1074

non ho riscontrato alcun problema nell'algoritmo e ho risolto il problema a mano e ho trovato anche 1064, qualcuno sa se la soluzione è sbagliata, sto interpretando la domanda sbagliata, o se c'è solo un difetto nell'algoritmo ?

Answer 1

tuo problema è che l'algoritmo è un algoritmo greedy, sempre trovando massimi locali. Sfortunatamente questo fa sì che manchino numeri più alti in basso perché sono direttamente al di sotto dei numeri più bassi. Ad esempio, se il triangolo fosse solo a 3 livelli, il tuo algoritmo selezionerebbe 75 + 95 + 47 = 217, mentre la risposta corretta è 75 + 64 + 82 = 221.

L'algoritmo corretto proverà ogni percorso e sceglierà quello con il più alto totale, o percorsi di calcolo dal basso verso l'alto (che ti permette di evitare di provarli tutti, quindi di essere molto più veloce). Dovrei aggiungere che lavorare dal basso verso l'alto non è solo molto più veloce (O (n^2) invece di O (2^n)!), Ma anche molto più facile da scrivere (l'ho fatto in circa 3 righe di codice) .

Answer 2

Hai scritto un greedy algorithm, che non credo soddisfi i requisiti qui. Ecco un rapido esempio per dimostrare questo punto:

1 
2 1 
1 1 100 

Usando l'algoritmo si raggiunge una somma di 4, anche se la soluzione ottimale è 102.

Answer 3

Ecco una descrizione grafica:

Answer 4

Ecco cosa basso verso l'alto metodo di Belisario descrive - con il triangolo banale dato di problema 18 - appare come, nel caso in cui l'immagine nel suo post è fonte di confusione per chiunque altro.

 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 (non necessariamente il migliore) approccio:

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)); 
    }