Python 杆切割算法 - 变体

Question

在我的一节课上，我被问到这是一个脑筋急转弯，但我无法弄明白(这不是家庭作业问题，只是其中一位助教给我们的一个脑筋急转弯让我们思考)。

给你一根杆，上面有 n 个要切割的点，例如 [1,5,11]，以及杆的总长度，例如 20。你还被告知切割 a 的费用杆等于杆的长度。我们想要找到在所有给定的切割中切割杆的最小成本以及将导致最优成本的那些切割的顺序。

例如，要在位置 5 切割一根长度为 20 的杆，您需要花费 20 美元，最终您会得到 2 根原木，一根长度为 5，一根长度为 15。

或者在另一个例子中，如果你在位置 5 切割一根长度为 25 的杆，然后在位置 10 切割，那么在位置 5 切割它需要花费 25 美元，剩下一根长度为 5 的杆和一根长度为 20 的杆，然后再花费 20 美元在第 10 个位置进行切割，这样在两个位置进行切割的总成本为 45 美元。但是，如果您在位置 10 处切割杆，然后在位置 5 处切割，则需要花费 25 美元 + 10 美元 = 35 美元。

最后，我们想要返回在所有给定的切割中切割杆的最小成本以及将导致最优成本的那些切割的顺序。

我试图为这个问题想出一个递归的解决方案，但总是空手而归。想法？任何帮助表示赞赏。谢谢!

Answer 1

我认为切杆问题的要点在于贪心算法不会总是产生最优解 - 这个变体似乎证明了同样的观点。

考虑在 [13,25,26] 处切割 L=50 杆。选择最接近中点的切割的算法会告诉您执行 [25, 13, 26]，总成本为 50 + 25 + 25 = 100。我们可以通过执行 [26, 13, 25] 来改进它，总成本为 50 + 26 + 13 = 89。

编辑:

即。您可以在 P=26 处切割 L=50 杆，从而得到需要的 L=24 (P=26->50) 杆没有更多的切割和需要在 [25,13] 处切割的 L=26 (P=0->26) 杆。然后在 P=13 处切割 L=26 杆，得到一个 L=13 (P=0->13) 杆，不需要更多切割和第二个 L=13 (P=13->26) 杆需要在 P=25 处进行最终切割。然后进行最终切割，产生的成本是每个阶段切割的杆的长度总和 (50 + 26 + 13)。

通常提出的备选方案是自上而下和自下而上的技术，这些技术的效率通常取决于所涉及的逻辑(对于您试图最大化销售成本的传统杆切割问题，自下而上是首选，因为它减少了递归调用)。