algorithm - 在最短时间内获得所有苹果

Question

有 M 个苹果(0<=M<=7)，每个苹果都在直路上的不同位置。

每个苹果都在时间限制后死亡。你必须拿走所有 M 个苹果。

所以你需要找出在苹果腐烂的最后期限之前你应该采取的顺序，并从最合适的位置开始。

一个苹果 j 位于距离道路最左端 d[j] 处。取苹果所需的时间是瞬时的，并假设可以在 1 单位时间内走完一个单位距离。找到您可以通过的最短时间拿走所有的苹果。

例子:让它们是 5 个苹果，下面的五行显示成对的，每对显示

(distance ,time to perish)
(1,3)
(3,1)
(5,8)
(8,19)
(10,15)

此处最短时间为 11。

编辑:如果 M 变为更大的值(例如 50 或 100)怎么办？

很明显，暴力是行不通的

Answer 1

我想我以前在这里见过非常类似的东西，但我现在找不到它:我会尝试根据我的内存重建一些东西。我将忽略给定的固定数量的苹果。

最好的答案能在队伍内部的苹果上完成吗？假设是这样，那么就在你拿起最后一个苹果之前，你已经拿起了它两边的苹果。但是你一定是从最后一个苹果的一侧走到了另一侧，所以你最好在经过它时捡起现在是最后一个苹果的东西。所以最好的解决方案必须是拿起最左边的苹果或最右边的苹果。

假设您知道为最左边的 N-1 个苹果解决问题并前往最右边的 N-1 个苹果的最佳可能成本。然后，您可以计算出以最右边的苹果结束的解决方案的最佳可能成本 - 它只是 N-1 + 可能的旅行成本和移动一步的成本。给定类似的信息，您可以计算出以最左边的苹果结束的解决方案的最佳可能成本。鉴于这两个成本，您可以计算出拾取所有 N 个苹果然后在必要时移动到这 N 个苹果中最左边(最右边)的苹果的最佳可能成本。

这显然是朝着动态编程或内存解决方案发展的方向。有少于 2N^2 形式的子问题“在解决问题的约束下找到 k 个连续间隔的最小成本，然后在必要时移动到那些 k 个苹果的最左边(最右边)”。给定大小为 k 的问题的最佳解决方案，您可以计算出大小为 k+1 的问题的最佳解决方案。因此，这可以使用动态规划来解决，方法是使用大小为 k 的条目构建所有部分解决方案的表来构建大小为 k+1 的条目，或者通过内存，在解决大小为 k 的问题时使用递归来询问大小为 k 的解决方案+1，但是建立一个到目前为止找到的解决方案表，这样您就不必两次解决相同的子问题。在任何一种情况下，所花费的时间都会增加为 N 中的某个多项式，这比 N! 便宜。