渡轮装载问题
我对下面提到的算法问题有困难：
某港口有一艘三车道的渡轮，前面排着N个队列 车辆。每个都有指定的长度（以厘米为单位）。我们也知道 轮渡的长度 (L)。我们必须提出一种算法，它能够 将队列中的最大数量的汽车装载到渡轮上。每辆车可以选择走三个车道之一：左车道、中间车道或右车道。汽车必须按顺序处理 - 对于每辆车（从前面开始），我们必须决定它将行驶到哪条车道上。如果在我们结束时没有足够的可用空间容纳队列前面的汽车。剩余的车辆等待下一班渡轮。
贪心方法（首次适应）并不是在每种情况下都是最有效的（例如，如果 L 是 5 并且我们有队列 5 2 2 3 3）。因此，我试图找出如果我们将其视为动态规划问题的解决方案是什么。我仍然在尝试找到任何算法，但我所知道的所有动态算法（尤其是来自算法简介）似乎都不适合这个问题。
预先感谢您的任何建议。 :)
I have a difficulty with an undermentioned algorithmic problem:
There is a three-lane ferry in a port and in front of it there is a queue of N
vehicles. Each of them has got specified lenght in cm. We also know
the lenght (L) of the ferry. We have to propose an algorithm, which enables to
load the ferry with the maximum amount of cars from the queue. Each car can choose between taking one of the three lanes: left, center or right. Cars have to be processed in order - for each car (starting from the front) we have to decide on which lane it will drive onto. If there is no enought free space for the car being in the front of the queue at the moment we finish. Remaining cars wait for the next ferry.
Greedy method (first-fit) isn't the most efficent in every case (e.g. if L is 5 and we have the queue 5 2 2 3 3). Thus I were trying to figure out what is the solution if we will think of it as an dynamic programming problem. Still I'm trying to find any, but all dynamic algorithms I know (especially from the Introduction to Algorithms) seem not to fit that problem.
Thank you in advance for any suggestions. :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，请注意此问题与背包问题之间的相似之处，即分区问题，以及装箱问题。
这提出了伪多项式时间动态规划解决方案。在每一个问题中，我们都记录了小于我们感兴趣的尺寸的背包的最佳解决方案。在这种情况下，我们的背包是三个车道。现在我希望这个算法还没有离你太远。
我不会给你完整的答案，因为这是 UVa Online 的问题法官。不过，我希望这能让您朝着正确的方向前进。有很多关于如何解决背包相关问题的信息。
First, notice the similarities between this problem and the knapsack problem, the partition problem, and the bin packing problem.
This suggests a pseudopolynomial time dynamic programming solution. In each of those problems, we kept track of the optimal solution for a knapsack of every size less than the one we're interested in. In this case, our knapsacks are the three lanes. Now I hope the algorithm isn't too far from your mind yet.
I'm not going to give you the complete answer since this is a problem from UVa Online Judge. However I hope this puts you in the right direction. There is a lot of information out there on how to solve knapsack-related problems.