项目欧拉问题67：在100行三角形中找到最大成本路径 [英] Project Euler problem 67: find maximum cost path in 100-row triangle

问题描述

在项目欧拉的问题67 中有一个三角形给出，它包含100行。例如

In Project Euler's problem 67 there is a triangle given and it contains 100 rows. For e.g.

        5
      9  6
    4   6  8
  0   7  1   5

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

现在我必须找到从顶部到在给定的100行三角形中的底部。

Now I have to find the maximum total from top to bottom in given 100 rows triangle.

我正在考虑应该使用哪种数据结构，以便有效解决问题。

I was thinking about which data structure should I use so that problem will get solved efficiently.

推荐答案

您想将其存储为有向无环图。节点是三角形数组的条目，从 i 到 j iff j 是下一行，并且直接左边或右边 i 。

You want to store this as a directed acyclic graph. The nodes are the entries of your triangular array, and there is an arrow from i to j iff j is one row lower and immediately left or right of i.

现在，您需要在此图中找到最大重量定向路径（顶点权重之和）。一般来说，这个问题是NP完整的，但是，如templateatetypedef所指出的，DAG有高效的算法; 这里是一个：

Now you want to find the maximum weight directed path (sum of the vertex weights) in this graph. In general, this problem is NP-complete, however, as templatetypedef points out, there are efficient algorithms for DAGs; here's one:

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

这个工作，您将需要将路径的长度加权到目标节点的大小（因为所有路径都包含源，这很好）。

To make this work, you will need to weight the length of the path to be the size of the target node (since all paths include the source, this is fine).

这篇关于项目欧拉问题67：在100行三角形中找到最大成本路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！