c# - 将列表划分为子集

Question

我有一个项目列表，我想将其分成子集。为了便于讨论，我们假设它们是文件。我希望每个子集最多包含 5 个文件，并且尽可能使子集中文件的总大小小于 1 MB。如果单个文件超过 1MB，则它本身应该属于一个子集。

我用一种稍微更通用的形式写了这篇文章，使用通用的“项目指标”而不是文件大小。但我怀疑有更简单和/或更好的方法来做到这一点。有什么建议么？

这是我得到的:

public static IEnumerable<IEnumerable<T>> InSetsOf<T>(this IEnumerable<T> source, int maxItemsPerSet, int maxMetricPerSet, Func<T, int> getMetric)
{
    int currentMetricSum = 0;
    List<T> currentSet = new List<T>();

    foreach (T listItem in source)
    {
        int itemMetric = getMetric(listItem);

        if (currentSet.Count > 0 && 
            (currentSet.Count >= maxItemsPerSet || (currentMetricSum + itemMetric) > maxMetricPerSet))
        {
            yield return currentSet;

            //Start a new subset
            currentSet = new List<T>();
            currentMetricSum = 0;
        }

        currentSet.Add(listItem);
        currentMetricSum += itemMetric;
    }

    //Return the last set
    yield return currentSet;
}

Answer 1

装箱是一个 NP-hard 问题。获得最佳解决方案的唯一方法是测试所有组合。如果有固定数量的不同大小，则可以使用动态规划系统地完成(有一个 answer on SO 带有针对这种情况的示例代码)，但这种算法的运行时间很糟糕。

这意味着您应该寻找一种启发式算法，它可以让您在合理的时间内接近最佳解决方案。您的算法(首次拟合)是一个很好的起点。不费吹灰之力，就可以通过减小尺寸对项目进行预分类来略微改进。然而，还有其他几种或多或少复杂的启发式方法可以提高速度和结果。

A Google search将此作为结果之一返回:Basic analysis of bin-packing heuristics (有一个 paper 分析结果)。显然，带有 bin 查找表的最佳拟合算法在合理的运行时间下提供了良好的结果。