英文:
How to partition a list so that the sums of the sublists are roughly equal
问题
我有一个排序好的包含2000个或更少对象的列表，每个对象都有一个数值。我想知道如何编写（用Java）一种方法，将这个列表分割成子列表，每个子列表大约包含200个对象（有一定的余地），使得每个子列表的值之和大致相等。
即使完整的列表少于2000个对象，我仍希望每个子列表大约包含200个对象。谢谢！
英文:
I have a sorted list of 2000 or fewer objects, each with a numerical value. I'm wondering how I can write (in Java) a way so split this list into sublists, each of roughly 200 objects (with fair leeway) such that the sum of the values of each sublist are roughly equal.
Even if the full list has fewer than 2000 objects, I still want the sublists to be roughly 200 objects each. Thank you!
答案1
得分: 1
以下是一个快速而粗糙的贪婪方法，应该能够很好地工作。
首先，确定你最终将得到多少个列表。将其称为 m。
将你的对象分成 m 组，可能会有一个较小的组，其中的值最接近0。
按最大值和最小值之间的差值降序排列你的组。
将你的组分配给你的列表，最大的对象放入总和最低的组中，接下来的最大对象放入下一个总和最低的组中，依此类推。
完成后，你将获得合适大小的列表，其差异相对较小。
（使用动态规划可以做得更好。但编写起来也更难。https://stackoverflow.com/questions/59505520/how-to-constrain-items-with-multiple-randomly-selected-positions-so-that-the-ave/59506930#59506930 可能会给你一些关于如何做到这一点的思路。）
英文:
Here is a quick and dirty greedy approach that should work well.
First, decide how many lists you will wind up with. Call that m.
Break your objects into groups of m, with the one possibly smaller group being the values closest to 0.
Order your groups by descending difference between the biggest and the smallest.
Assign your groups to your lists, with the largest object going into the group with the lowest total, the next largest the next lowest, and so on.
When you are done, you will have lists of the right size, with relatively small differences.
(You can do better than this with dynamic programming. But it will also be harder to write. https://stackoverflow.com/questions/59505520/how-to-constrain-items-with-multiple-randomly-selected-positions-so-that-the-ave/59506930#59506930 may give you some ideas about how to do that.)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论