algorithm - 自动对齐表格中的元素

Question

我需要制定一个算法，通过使用尽可能少的行数来对齐表中的元素。

需要蜜蜂排序的元素应该保持水平位置/对齐

像这样:[

我希望有人已经这样做了。谢谢!

Answer 1

澄清一下:我假设您的意思是每个项目都必须放在一行中，并且只能放在一行中(它不能分解到下一行)，但它们可以水平移动。

启发式/天真地，我会这样做:

• 按长度对元素进行排序。
• 尝试通过天真地挑选(从最长到最短)项目来填充第一个空闲行，直到该行已满或找不到更多匹配元素。
• 重复直到完成所有元素。

这将(相对)快速完成(在 O(nlogn) 和 O(n^2) 之间的某个位置，具体取决于启发式“捷径”)，但会留下比必要更多的漏洞，否则会出现非最佳解决方案。

我敢打赌这个问题等同于经典的 NP 完全问题之一 https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems ，因此您可能找不到实用的非启发式解决方案。