Задача 67 проекта Эйлера: найти путь максимальной стоимости в 100-рядном треугольнике

В задаче 67 проекта Эйлера задан треугольник, содержащий 100 строк. Например, 

        5
      9  6
    4   6  8
  0   7  1   5

I.e. 5 + 9 + 6 + 7 = 27.

Теперь я должен найти максимальную сумму сверху вниз в данном треугольнике из 100 строк.

Я думал о том, какую структуру данных я должен использовать, чтобы эта проблема была решена эффективно.

5 2
data-structures puzzle

5 ответов:

Вы хотите сохранить это в виде направленного ациклического графа. Узлы-это элементы вашего треугольного массива, и есть стрелка от i до j, если j находится на одну строку ниже и сразу слева или справа от i.

Теперь вы хотите найтимаксимальный вес направленного пути (сумма весов вершин) в этом графе. В целом, эта задача является NP-полной, однако, как указывает templatetypedef, существуют эффективные алгоритмы для DAG; Вот один : 
algorithm dag-longest-path is
    input: 
         Directed acyclic graph G
    output: 
         Length of the longest path

    length_to = array with |V(G)| elements of type int with default value 0

    for each vertex v in topOrder(G) do
        for each edge (v, w) in E(G) do
            if length_to[w] <= length_to[v] + weight(G,(v,w)) then
                length_to[w] = length_to[v] + weight(G, (v,w))

    return max(length_to[v] for v in V(G))

Чтобы сделать эту работу, вам нужно будет весить length пути, чтобы быть размером целевого узла (так как все пути включают источник, это нормально).

4

Какой язык вы используете?

Многомерный массив, вероятно, является лучшим способом хранения значений, тогда в зависимости от языка существуют варианты хранения указателей или ссылок на то, где в массивах вы находитесь.

1

Чтобы построить ответ @Matt Wilson, использование двумерного массива для хранения чисел было бы довольно простым решением. В вашем случае вы бы закодировали треугольник 

      5
    9  6
  4   6  8
0   7  1   5

Как массив

[5][ ][ ][ ]
[9][6][ ][ ]
[4][6][8][ ]
[0][7][1][5]

Отсюда узел в позиции (i, j) имеет детей в (i + 1, j) и (i + 1, j + 1) и родителей в позиции (i - 1, j) и (i - 1, j - 1), предполагая, что эти индексы допустимы.

Преимущество этого подхода заключается в том, что если ваш треугольник имеет высоту N, то требуемое пространство для этого подхода N2, что всего лишь в два раза меньше пространства N(N + 1) / 2, необходимого для фактического хранения элементов. Связанная структура, такая как явный граф, несомненно, будет использовать больше памяти, чем это.

1

Я считаю, что это проблема проекта Эйлера.

Он не может быть представлен двоичным деревом. Любой вид графа также является избыточным, хотя проблема может быть решена с помощью алгоритма длинного пути в направленных ациклических графах. Правка: неважно, это полезно только в том случае, если взвешены ребра, а не узлы.

Двумерного вектора (например, vector<vector<int> >) более чем достаточно для представления таких треугольников, и существует простое решение, использующее такое представление.

0
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>

int main() { 
    std::vector<std::vector<int> > lines;
    lines.resize(100);
    std::ifstream input("triangle.txt");

    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < i + 1; j++) {
            std::string number_string;
            input >> number_string;
            std::istringstream temp(number_string);
            int value = 0;
            temp >> value;
            lines[i].push_back(value);
        }
    } 
    std::vector<int> path1;
    path1.resize(100);
    std::vector<int> path2;
    path2.resize(100);

    for (int i = 0;i < 100;i++) 
        path1[i] = lines[99][i];

    for (int i = 98; i >= 0;i--) {  
        for(int j = 0;j < i+1;j++) {
            if(path1[j] > path1[j + 1]){
                path2[j] = path1[j] + lines[i][j];
            } else{
                path2[j] = path1[j + 1] + lines[i][j];
            }
        }
        for (int i = 0;i < 100;i++) 
            path1[i] = path2[i];
    }
    std::cout << path1[0] << std::endl;
}
0