我有一个有序列表，表示光纤电缆上的终端，其中每个终端都有许多端口（例如4、8、12）提供一根光纤电缆，该电缆将为每个终端端口提供不同的光纤股该电缆可包含144股编号为1-144的光纤，每股由12根光纤组成我想将光纤股分配给终端端口，这样在任何一个终端上，我都不需要访问来自多个组的光纤。我想把光纤尽可能按端子的顺序排列。我想尽量避免未使用的纤维股。
例如，如果我有端口大小分别为12、8、12、6、6、12的终端A、C、D、E、F，我希望算法生成结果A（1-12）、B（49-56）、C（13-24）、D（25-30）、E（31-36）、F（37-48）
有人能提出一个理想的算法吗？
最佳答案
问题是bin packing的排序方面。单独装箱是np难的，所以我建议的精确算法的运行时间不是多项式。希望它还是有用的。
第一步是生成所有可能的组。这里有一些python来演示我的意思。
def allgroups(terminals, fibrecount=12, groupsofar=[]):
if terminals: # is nonempty
terminal = terminals.pop() # last element
if terminal.portsize <= fibrecount:
groupsofar.append(terminal)
yield from allgroups(terminals, fibrecount - terminal.portsize, groupsofar)
groupsofar.pop() # terminal
yield from allgroups(terminals, fibrecount, groupsofar)
terminals.append(terminal)
elif groupsofar:
yield groupsofar
第二步是使用Algorithm X生成所有可能的分组，第三步是通过动态编程评估每个分组。你没有说“尽可能按照终端的顺序”意味着什么，所以我会尽量减少inversions。实际上，只要目标有最优子结构，即给定同一组的两个序，不管其他组是如何排列的，一个总是比另一个好。
在运行动态程序之前，计算每对组的倒数（如果第一个出现在第二个之前）。这意味着在第一组上迭代的外部循环和在第二组上迭代的内部循环，计算第一组中的终端应该出现在第二组中的终端之后的次数。现在，对于非递减顺序的组的每个子集，确定该子集的最佳顺序。由于最优子结构，最优顺序从子集中的某个组开始，到我们已经计算出的余数的最优解结束。在所有选择中最小化哪个组优先。
关于algorithm - 将项目(光纤终端)分组到最适合容器(光纤缓冲区)的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16991865/