鉴于我们必须达到所有点,我真的不明白如何最好地实现找到最小长度总和的算法。
任务的本质:
我们有n个顶点,还有一个数组a等于n,是一个数,这就是点之间的距离。我们需要能够找到所有长度的最小总和,同时我们至少学习所有点 1 次。
例子:
我们n = 3还有一个数组(n 个元素)a = { 1, 2, 3 },其中a[0]是 1 和 2 之间a[1]的距离,是 2 和 3 之间的距离,a[2]这就是 3 和 1 之间的距离。
事实证明,选项是这样的,我们只取长度1 - 2和2 - 3,这会捕获所有点,同时给出等于 3 的最小长度总和。
示例#2:
为了更好地理解,我将举一个更复杂的示例。我们n = 6还有一个数组a = { 1, 2, 5, 1, 1, 6 },其中a[0]是1到2a[1]的距离,是2到3a[2]的距离,这是3到4a[3]的距离,这是4到5a[4]的距离,这是5到6的距离,a[5]这是 6 和 1 之间的距离。
事实证明,选项是这样的,我们只取长度1 - 2, 2 - 3, 4 - 5,5 - 6这会捕获所有点,同时给出等于 5 的最小长度总和。

您能建议在这种情况下进行的最佳方法吗?我尝试了贪心算法,但它不起作用,因为有一个错误。如果可能的话,如果有伪代码会很好......




