java - 如何对列表进行分区以使子列表的总和大致相等

Question

我有一个包含 2000 个或更少对象的排序列表，每个对象都有一个数值。我想知道如何（用Java）编写一种方法，将这个列表分成子列表，每个子列表大约有200个对象（有公平的余地），这样每个子列表的值的总和大致相等。

即使完整列表的对象少于 2000 个，我仍然希望每个子列表大约有 200 个对象。谢谢！

标签： javalistalgorithmsortingsortedlist

Answer 1

这是一种快速而肮脏的贪婪方法，应该可以很好地工作。

首先，决定你最终会得到多少个列表。叫那个m。

将您的对象分成 组m，其中一个可能较小的组是最接近 0 的值。

按最大和最小之间的降序排列您的组。

将您的组分配到您的列表中，最大的对象进入总数最低的组，次大的进入次低的组，依此类推。

完成后，您将获得大小合适的列表，并且差异相对较小。

（你可以用动态编程做得比这更好。但它也会更难写。 如何约束具有多个随机选择位置的项目，以便每个项目的平均位置在一定范围内可能会给你一些关于如何做的想法那。）