algorithm - 最小粗糙度自动换行的近似算法

Question

我正在寻找一种有效的算法(理想情况下是类似 C 的伪代码)来为以下分区问题提供近似解。给定一个序列 S = {a_i : i=1,...,n} 和一个边界 < em>B，将 S 划分为一些 m 的连续子序列，如下所示。对于每个 k，设 s_k 为第 k 个子序列的元素之和。分区必须满足:

1. s_k ≤ B 对于每个 k(假设 B 和 a_i 总是可能的)
2. m 是最小的(没有更小的分区满足 #1)；
3. 某些分散度量(例如，s_k 之间的方差或最大成对差异)在大小为 的所有分区中最小米。

我知道这与minimum raggedness word wrap algorithm密切相关.我正在寻找可以为 n(小于 15)的小值提供“足够好”的解决方案，而无需像动态编程那样拔出重型弹药，但也比蛮力快一点。

Answer 1

设 S 表示所有项目的总和，n 表示项目的数量。如果您将项目放在 m 行上，则每行至少有 S/m 重量。因为 S/m ≤ B，所以 m ≥ S/B。我将从 ceiling(S/B) 作为 m 的值开始，然后将 m 增加 1，直到找到解决方案。

当设置了 m 并给出了 n 时，这只是递归搜索正确边界的问题。您一条一条地(递归地)猜测线之间的边界，并在解决方案变得不可行时回溯。如果找到解决方案，请将其存储以供引用，因为它可能是最好的分散方式。最终你选择了最好的解决方案。如果没有解决方案，则将 m 增加 1 并重做。