Question Projet Euler 18


Hey, a travaillé au projet Euler, et celui-ci me pose des problèmes

En commençant en haut du triangle ci-dessous et en passant aux nombres adjacents sur la ligne ci-dessous, le total maximum de haut en bas est 23.

3

7 4

2 4 6

8 5 9 3

C'est-à-dire 3 + 7 + 4 + 9 = 23.

Trouvez le total maximum de haut en bas du triangle ci-dessous:

...

REMARQUE: Comme il n'y a que 16384 routes, il est possible de résoudre ce problème en essayant chaque route. Cependant, le problème 67 est le même défi avec un triangle contenant une centaine de lignes; il ne peut pas être résolu par force brute, et nécessite une méthode intelligente! ; o)

voici l'algorithme que j'ai utilisé pour le résoudre

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

maintenant chaque fois que je l'exécute, il arrive avec 1064, seulement 10 de moins que la solution - 1074

Je n'ai pas trouvé de problème avec l'algorithme et j'ai fait le problème à la main et 1064, n'importe qui sait si la solution est fausse, j'interprète mal la question ou s'il y a juste une faille dans l'algorithme?


13
2018-01-23 06:19


origine


Réponses:


Votre problème est que votre algorithme est un algorithme glouton, trouvant toujours des maxima locaux. Malheureusement, cela entraîne des nombres plus élevés en bas, car ils sont directement inférieurs aux chiffres les plus bas. Par exemple, si le triangle ne comportait que 3 niveaux, votre algorithme sélectionnerait 75 + 95 + 47 = 217, tandis que la réponse correcte serait 75 + 64 + 82 = 221.

L'algorithme correct essaiera chaque chemin et choisira celui avec le total le plus élevé, ou calculera les chemins à partir du bas (ce qui vous permettra d'éviter d'essayer tout le monde, donc d'être beaucoup plus rapide). Je devrais ajouter que travailler de bas en haut n'est pas seulement beaucoup plus rapide (O (n ^ 2) au lieu de O (2 ^ n)!), Mais aussi beaucoup plus facile à écrire (je l'ai fait en environ 3 lignes de code) .


7
2018-01-23 06:35



Voici une description graphique:

enter image description here


13
2018-01-23 07:16



Voici à quoi ressemble la méthode ascendante décrite par belisarius - en utilisant le triangle trivial donné dans le problème 18 - juste au cas où l'image dans son article serait déroutante pour quelqu'un d'autre.

      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

12
2018-06-30 23:47



Vous avez écrit un algorithme gourmand, qui selon moi ne correspond pas aux exigences ici. Voici un exemple rapide pour démontrer ce point:

  1
 2 1
1 1 100 

En utilisant votre algorithme, vous atteindrez une somme de 4, bien que la solution optimale soit 102.


6
2018-01-23 06:33



Approche récursive (pas nécessairement la meilleure):

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

-1
2017-08-14 20:16