algorithm - 来自子序列部分的序列？

Question

假设我有以下项目:

 1;2;3;4;5;[1,2];[3,4];[1,2,3];[2,3,4]

(注意:我没有所有可用的排列，只有一部分)

每个项目都有一个与之相关的分数。现在的任务是从可用部分构建序列:

1,2,3,4,5

有很多方法可以创建序列:

the simplest : 1,2,3,4,5
or : [1,2],[3,4], 5
or : 1,[2,3,4], 5
or : [1,2],[3,4],5
or : ........

正确的序列应该是得分最高的序列。

你会怎么做？图表？

Answer 1

使用递归过程遍历图形。每个子序列都是一个节点。边连接源节点的末尾整数与目的节点的第一个整数相邻的节点。

例如，您有从 [1] 到 [2] 和 [2, 3, 4] 的边。您还有从 [1, 2] 到 [3] 和 [3, 4] 的边。

这将问题简化为 Dijkstra 算法，通过带加权边的图找到最佳路径。