将可变大小的项目平衡为粗略平衡的集合的算法
我正在寻找一种算法，将不同大小的项目列表分成“N”个类似大小的组。
具体来说，我正在使用C＃中的ASP.NET站点，其中有一个（数据库检索的）字符串列表。 琴弦的长度各不相同。 我有一组需要显示字符串的列。 我需要一种算法来找到最平衡的集合（项目顺序无关紧要），以允许最终的列尽可能平衡。
抽象示例：
创建3列。
要分发的项目：
- Item A - height 5 - Item B - height 3 - Item C - height 7 - Item D - height 2 - Item E - height 3 期望的输出：
Column 1: Item A, Item D Column 2: Item C Column 3: Item B, Item E
最快的事情可能就是将每个新项目插入最小的列表中（其中“最小”是列表中所有项目大小的总和）。
这似乎是包装盒（或装箱包装）问题的变体，在这种情况下，您尝试将可变大小的项目集合装入尽可能少的容器中：
http://en.wikipedia.org/wiki/Bin_packing_problem
根据您的项目大小，您可能会相当简单地强制解决方案，寻找具有最小尺寸差异的组合。 对于较大的集合，这变得非常困难，并且使用“简单”算法可能会让您更接近一个好的答案。
看看作业车间调度算法 ，我们有许多不同大小的工作要在机器上分配，这样总的生产时间就很短。
这是另一个可以创建所需长度组的版本。
public static List> Balance(List input, int desiredLimit) { var result = new List>(); if (input.Count > 0) { var values = new List (input); values.Sort(); var start = 0; var end = values.Count - 1; var orderedValues = new List (values.Count); while (start < end) { orderedValues.Add(values[start]); orderedValues.Add(values[end]); start++; end--; } if (values.Count % 2 != 0) { orderedValues.Add(values[values.Count / 2]); } var total = 0; var line = new List (); for (int i = 0; i < orderedValues.Count; i++) { var v = orderedValues[i]; total += v; if (total <= desiredLimit) { line.Add(v); } else { total = v; result.Add(line); line = new List () { v }; } } result.Add(line); } return result; }
尝试非常基本的东西
public static List> Balance(List input) { var result = new List>(); if (input.Count > 0) { var values = new List (input); values.Sort(); var max = values.Max(); var maxIndex = values.FindIndex(v => v == max); for (int i = maxIndex; i < values.Count; i++) { result.Add(new List { max }); } var limit = maxIndex; for (int i = 0; i < limit / 2; i++) { result.Add(new List { values[i], values[(limit - 1) - i] }); } if (limit % 2 != 0) { result.Add(new List { values[limit / 2] }); } } return result; }
如果需要按两个元素分组，可以使用此方法。 您可以将其更改为组元素，直到达到预定义值（例如10）。 可能我会将其他版本发布到。
如果您有两列，这听起来像是分区问题的应用。 问题是NP完全，但有一个动态编程解决方案是伪多项式时间。 http://en.wikipedia.org/wiki/Partition_problem
如果增加列数超过2，则没有伪多项式时间解决方案。 http://en.wikipedia.org/wiki/3-partition_problem