algorithm - 机器人和容器最小化问题，需要的方法

Question

鉴于此 problem :

You have a warehouse with M containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be 1 meter apart. You also have 2 robots that can pick up 1 piece of candy and transport it between any two containers.

The robots take instructions in the form of queries consisting of two integers, Ma and Mb, respectively. To execute a query, a robot travels to container Ma, picks up 1 candy, transports it to container Mb, and then stops at Mb until it receives another query.

Calculate the minimum total distance the robots must travel to execute N queries in order.

Note: You choose which robot executes each query.

最初我假设我应该简单地选择更接近的机器人来执行移动，但是这种方法在某些测试用例中失败了，谁能解释为什么这种方法对所有情况都无效，以及什么是正确的方法，谢谢。

示例输入和预期输出 here .

Answer 1

问题属于动态规划类别，您自己将问题标记为greedy(您的方法确实是贪婪的)。在某些情况下，给定查询的最小距离(局部最小值)对于完整的查询集(全局最小值)不是最优的。因此，您需要考虑机器人对查询的所有可能分配，但使用 DP 技术，这不是详尽的搜索。

我不想为您详细说明确切的解决方案，因为 DP 上有很多在线资源(制作二维成本表，跨列移动 = 机器人 1，跨行移动 = 机器人 2，找到通过表格的最佳路径，...)。但我想向您展示一个示例情况，其中贪婪方法是次优的。

• A 机器人 1
• B 机器人 2
• F查询起点
• T 查询结束点

用贪心法解决:

 (A)                  B
1 . . F . T . . . . . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
         (A)          B
2 . . . . . . F . T . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
                 (A)  B
3 F T . . . . . . . . . // A is closer to F, travels 8 (to F) + 1 (to T) = 9
    A                 B

总行驶距离:4 + 4 + 9 = 17。

最佳方法(可能有多个):

 (A)                  B
1 . . F . T . . . . . . // A takes query, travels 2 (to F) + 2 (to T) = 4
          A          (B)
2 . . . . . . F . T . . // B takes query, travels 4 (to F) + 2 (to T) = 6
         (A)      B
3 F T . . . . . . . . . // A takes query, travels 4 (to F) + 1 (to T) = 5
    A             B

总行驶距离:4 + 6 + 5 = 15。

请注意 B 接受了第二个查询，即使它不是最接近起点的。