Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to balance variably-sized items into roughly-balanced sets

I'm seeking an algorithm to split a list of items of varying sizes into "N" number of similarly-sized groups.

Specifically, I'm working on an ASP.NET site in C# where I have a (database-retrieved) list of strings. The strings are of varying lengths. I have a set of columns which need to display the strings. I need an algorithm that will find the most balanced sets (item order is irrelevant) to allow the final columns to be as balanced as possible.

Abstracted Example:

Creating 3 columns.

Items to distribute:

 - Item A - height 5
 - Item B - height 3
 - Item C - height 7
 - Item D - height 2
 - Item E - height 3

Desired output:

Column 1: Item A, Item D
Column 2: Item C
Column 3: Item B, Item E
like image 781
Gnosian Avatar asked Aug 26 '10 12:08

Gnosian


1 Answers

The quickest thing to do is probably just insert each new item into the smallest list (where "smallest" is the sum of the sizes of all the items in the list).

like image 160
TMN Avatar answered Oct 21 '22 16:10

TMN