将列表划分为子集

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 难题。获得最佳解决方案的唯一方法是测试所有组合。如果有固定数量的不同大小，则可以使用动态规划系统地完成（有一个关于SO的答案本例的示例代码），但是这种算法的运行时间非常糟糕。

这意味着您应该寻找一种启发式方法，让您在合理的时间内接近最佳解决方案。您的算法（首次拟合）是一个很好的起点。只需付出很少的努力，就可以通过减小尺寸对物品进行预分类来稍微改进。然而，还有其他几种或多或少复杂的启发式方法可以提高速度和结果。

Google 搜索返回以下结果之一：装箱启发式的基本分析（有一个 论文 分析结果）。显然，带有 bin 查找表的最佳拟合算法可以在合理的运行时间内提供良好的结果。

Answer 2

缺少 1MB 测试，但除此之外你的代码对我来说看起来还不错。我认为没有更好的方法可以做到这一点。