algorithm - 轮渡装载问题

Question

我对下面提到的算法问题有困难：

一个港口有一个三车道的渡轮，在它前面有N辆车的队列。他们每个人都有以厘米为单位的指定长度。我们也知道渡轮的长度 (L)。我们必须提出一种算法，该算法能够从队列中装载最大数量的汽车。每辆车都可以选择走三个车道之一：左、中或右。必须按顺序处理汽车 - 对于每辆汽车（从前面开始），我们必须决定它将驶入哪条车道。如果在我们完成时没有足够的空闲空间让汽车排在队列的前面。剩余的汽车等待下一个渡轮。

贪心方法（首次拟合）并不是在每种情况下都是最有效的（例如，如果 L 为 5 并且我们有队列 5 2 2 3 3）。因此，如果我们将其视为动态规划问题，我试图找出解决方案是什么。我仍然试图找到任何，但我知道的所有动态算法（尤其是来自算法简介）似乎都不适合这个问题。

提前感谢您的任何建议。:)

Answer 1

首先，注意这个问题与背包问题、分区问题和装箱问题的相似之处。

这提出了一个伪多项式时间动态规划解决方案。在这些问题中的每一个问题中，我们都会跟踪每个尺寸小于我们感兴趣的背包的最佳解决方案。在这种情况下，我们的背包是三个通道。现在我希望这个算法离你的想法还不算太远。

我不会给你完整的答案，因为这是来自UVa Online Judge的问题。但是，我希望这能让您朝着正确的方向前进。有很多关于如何解决背包相关问题的信息。