javascript - 算法题: Packing rods into a row

Question

好吧，这可能是个棘手的问题。它实际上是与我的实际应用程序相关的另一个类似问题的类比，但为了清楚起见，我将其简化为这个假设问题。开始了:

1. 我有一排鱼竿需要分类。因为是一条线，所以只需要关注1个维度。
2. 杆的长度和重量各不相同。重量和长度之间没有相关性。小杆可能非常重，而大杆可能非常轻。
3. 棒需要按重量分类。
4. 不过，真正的问题是，一些杆只能放置在距离线路起点不超过一定距离的地方，无论他们的体重。不过，在那之前的任何地方都可以。
5. 不保证约束之间的距离足够远，以防止受约束的杆被挤压成重叠的可能性。在这种情况下(希望很少见)，要么需要在其约束范围内以某种方式重新排列杆以创造所需的空间，要么可能需要找到理想的折衷解决方案(例如违反最小光杆的约束，因为示例)。
6. 有可能在未来的某个日期，除了长度限制之外，还可以添加额外的限制，以指示线内的特定(甚至是非妥协的)边界，其中杆 不能 重叠成。

我目前的解决方案没有考虑到后一种情况，它们听起来像是需要一些复杂的工作来解决。

请注意，这是针对客户端 Web 应用程序的，因此制定解决方案 apply to Javascript会有帮助!

Answer 1

如果可能的话，我建议将其表述为混合整数程序。如果您可以在此处对约束进行编码，则可以使用求解器来满足约束。有关此类方法的更多信息，请参阅此页面:

http://en.wikipedia.org/wiki/Linear_programming

如果您能以某种方式将它与 Javascript 接口(interface)，那么它可能被证明是一个优雅的解决方案。