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

Question

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

        5
      9  6
    4   6  8
  0   7  1   5

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

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

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

Answer 1

Вы хотите сохранить это как направленный ациклический граф . Узлы - это записи вашего треугольного массива, и есть стрелка от 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 пути, чтобы он соответствовал размеру целевого узла (поскольку все пути включают в себя источник, это нормально).

Answer 2

Если исходить из ответа @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, пространство, требуемое для этого подхода, равно N ² , что чуть меньше, чем вдвое больше требуемого пространства N (N + 1) / 2. на самом деле хранить элементы. Связанная структура, такая как явный граф, наверняка будет использовать больше памяти.

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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