0

我需要能够将一组已知大小的对象分配到 3 个组中。例如，给定一个如下所示的有序列表，我想找到两个划分或分离点来组成三个总和相似的组。

75, 67, 54, 40, 51, 48, 49, 47

每组的总和必须大致相等，并且第 2 组和第 3 组的总和不能超过第一组的总和超过定义的数量（例如 10）。理想情况下，第一组略大于其他组。项目的顺序不能更改。每个组由原始列表的连续元素组成。每个元素都放在一个组中。

在这种情况下，预期的解决方案是：

Groups: [75, 67], [54, 40, 51], [48, 49, 47]

Sums: 142, 145, 144

用例是根据前端布局中的已知高度预先计算（服务器端）优先故事到列中的分配。我已经有代码可以为内容提供足够接近的高度（按比例而言），但我正在努力寻找一种有效的分组方式。有充分的理由说明为什么不在前端这样做，但大概也可以在那里使用通用解决方案。

4

1 回答 1

1

鉴于您大约知道要分配给每个组的数量（总计 / 3），为什么不遍历列表并将对象分配给组 1 直到其总数达到（总计 / 3），然后对组 2 执行相同操作，然后其余的进入第 3 组。最终结果可能不适合您的参数，例如第 2 组可能超过第 1 组超过 epsilon，在这种情况下，如果需要，您可以将第 3 组中的一个或两个元素交换到第 2 组，然后如果需要将一个或两个元素从第 2 组交换到第 1 组。整个事情应该在 O(n) 中运行，并期望您最后需要交换少于十几个元素。

于 2013-05-17T20:22:20.743 回答