将不同大小的项目平衡为大致平衡的集合的算法

Question

我正在寻找一种算法，将不同大小的项目列表拆分为“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

Answer 1

最快的方法可能是将每个新项目插入到最小的列表中（其中“最小”是列表中所有项目的大小之和）。

Answer 2

这似乎是包装盒（或装箱）问题的一个变体，您尝试将可变大小的物品集合放入尽可能少的容器中：

http://en.wikipedia.org/wiki/Bin_packing_problem

根据你的项目集的大小，你可能可以相当简单地暴力破解一个解决方案，看看用于尺寸差异最小的组合。对于较大的集合，这成为一个相当困难的问题，并且您可能会更好地使用“简单”算法，让您接近一个好的答案。

Answer 3

看看作业车间调度算法，其中我们有许多不同大小的作业分散在机器上，使总生产时间最短。

Answer 4

这是另一个版本，可以创建所需长度的组。

        public static List<List<int>> Balance(List<int> input, int desiredLimit)
    {
        var result = new List<List<int>>();

        if (input.Count > 0)
        {
            var values = new List<int>(input);
            values.Sort();

            var start = 0;
            var end = values.Count - 1;
            var orderedValues = new List<int>(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<int>();

            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<int>() { v };
                }
            }
            result.Add(line);
        }

        return result;
    }

Answer 5

尝试一些非常非常基本的

        public static List<List<int>> Balance(List<int> input)
    {
        var result = new List<List<int>>();

        if (input.Count > 0)
        {
            var values = new List<int>(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<int> { max });
            }
            var limit = maxIndex;
            for (int i = 0; i < limit / 2; i++)
            {
                result.Add(new List<int> { values[i], values[(limit - 1) - i] });
            }
            if (limit % 2 != 0)
            {
                result.Add(new List<int> { values[limit / 2] });
            }
        }

        return result;
    }

方法如果您需要按两个元素进行分组，则可以使用此方法。您可以将其更改为对元素进行分组，直到达到预定义值（例如 10）。也许我会将其他版本发布到。

Answer 6

如果您有两列，这听起来像是分区问题的应用。该问题是 NP 完全问题，但存在伪多项式时间的动态规划解决方案。
http://en.wikipedia.org/wiki/Partition_problem

如果您将列数增加到超过二、则不存在伪多项式时间解。
http://en.wikipedia.org/wiki/3-partition_problem

Answer 7

这是实现接受的答案的通用代码：

• 只需将每个新项目插入最小的列表

• 首先对项目进行排序（从大到小），这将改善很多

   class Item { 内部 Item(int 重量) { 重量 = 重量; } 内部 int 权重 { 获取； } }
  
    [测试]
    公共无效测试1（）{
  
       var A = 新项目(5);
       var B = 新项目(3);
       var C = 新项目(7);
       var D = 新项目(2);
       var E = 新项目(3);
  
       Item[][] 结果 = AlgoToBuildBalancedPartition.Go(new[] { A, B, C, D, E }, t => t.Weight, 3);
       Assert.AreEqual(结果.Length, 3);
       Assert.Contains(C, 结果[0]);
       Assert.Contains(A, 结果[1]);
       Assert.Contains(D, 结果[1]);
       Assert.Contains(B, 结果[2]);
       Assert.Contains(E, 结果[2]);
    }
  
    //------------------------------------------------ --
  
    公共静态类 AlgoToBuildBalancedPartition {
  
       公共静态 T[][] Go(
              IEnumerable序列，
              Func;获取权重过程，
              int maxNbPartitions) 其中 T : 类 {
          Debug.Assert(!seq.IsNullOrEmpty());
          Debug.Assert(getWeightProc != null);
          调试.Assert(maxNbPartitions >= 2);
  
          var partitions = new List>(maxNbPartitions);
  
          T[] seqDescending = seq.OrderByDescending(getWeightProc).ToArray();
          int count = seqDescending.Length;
  
          for (var i = 0; i < count; i++) {
             T 项 = seqDescending[i];
             if (partitions.Count < maxNbPartitions) {
                Partitions.Add(new Partition(item, getWeightProc));
                继续;
             }
  
             // 获取权重最小的分区
             Debug.Assert(partitions.Count == maxNbPartitions);
             varpartitionWithMinWeight = 分区[0];
             for (var j = 1; j < maxNbPartitions; j++) {
                var 分区 = 分区[j];
                if (partition.TotalWeight >partitionWithMinWeight.TotalWeight) { 继续; }
                partitionWithMinWeight = 分区；
             }
  
             PartitionWithMinWeight.AddItem(项目);
          }
  
          返回partitions.Select(p => p.Items.ToArray()).ToArray();
       }
  
  
       私有密封类 Partition;其中 T : 类 {
          内部分区(T firstItem, Func getWeightProc) {
             调试.Assert(firstItem != null);
             Debug.Assert(getWeightProc != null);
             m_GetWeightProc = getWeightProc;
             添加项目（第一个项目）；
          }
          私有只读 Func m_GetWeightProc；
          内部列表项目{得到; } = 新列表();
          内部无效AddItem（T项）{
             调试.Assert(item != null);
             项目.添加(项目);
             TotalWeight += m_GetWeightProc(item);
          }
          内部 int TotalWeight { 获取；私人套装； } = 0;
       }
    }