讨论/技术交流/求解一个算法问题/

在n个城市中,对于每个i<j,有一条从城市i到城市j的道路要花费Tij的时间。两个旅行者马可(Marco)和波罗(Polo)希望在尽可能短的时间内穿越所有城市。换句话说,我们希望将城市分为两组,然后将一组分配给Marco,将另一组分配给Polo,以使它们的旅行时间总和最小化。 可以假定他们从集合中索引最小的城市开始旅行,并且他们以索引的升序(从最小索引到最大)旅行。算法的时间复杂度应为O(n^2)。
image.png
如题,求大佬指点

共 0 个回复
暂无回复