鉴于我们必须达到所有点,我真的不明白如何最好地实现找到最小长度总和的算法。
任务的本质:
我们有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 的最小长度总和。
您能建议在这种情况下进行的最佳方法吗?我尝试了贪心算法,但它不起作用,因为有一个错误。如果可能的话,如果有伪代码会很好......