# 如何分割一个列表，使子列表的总和大致相等

go评论36阅读模式

How to partition a list so that the sums of the sublists are roughly equal

# 问题

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

（使用动态规划可以做得更好。但编写起来也更难。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.)

• 本文由 发表于 2020年7月29日 03:04:55
• 转载请务必保留本文链接：https://go.coder-hub.com/63141132.html
• algorithm
• java
• list
• sortedlist
• sorting

go 42

go 62

go 39

go 40