我有一个项目列表,我想将其分成子集。为了便于讨论,我们假设它们是文件。我希望每个子集最多包含 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;
}
最佳答案
装箱是一个 NP-hard 问题。获得最佳解决方案的唯一方法是测试所有组合。如果有固定数量的不同大小,则可以使用动态规划系统地完成(有一个 answer on SO 带有针对这种情况的示例代码),但这种算法的运行时间很糟糕。
这意味着您应该寻找一种启发式算法,它可以让您在合理的时间内接近最佳解决方案。您的算法(首次拟合)是一个很好的起点。不费吹灰之力,就可以通过减小尺寸对项目进行预分类来略微改进。然而,还有其他几种或多或少复杂的启发式方法可以提高速度和结果。
A Google search将此作为结果之一返回:Basic analysis of bin-packing heuristics (有一个 paper 分析结果)。显然,带有 bin 查找表的最佳拟合算法在合理的运行时间下提供了良好的结果。
关于c# - 将列表划分为子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8594071/