将数字按降序分组

Question

我总是在与这些类型的算法作斗争。我有一种情况，我有一个运费的立方值，需要将这个值拆分成不同尺寸的纸箱，在这种情况下有三种尺寸可供选择，分别是0.12m3、0.09m3和0.05m3。几个例子；

假设总立方米为0.16立方米，我需要将这个值消耗到合适的纸箱中。我会有1箱0.12立方米，这剩下0.04立方米要消耗。这适合0.05立方米，所以我将有1箱0.05米，消耗现在已经完成。最终答案是1 x 0.12m3和1 x 0.05m3。

假设总立方米为0.32立方米，我最终会得到2 x 0.12立方米和1 x 0.09立方米。

我更喜欢c#或SQL中可以很容易地返回结果的东西。

非常感谢您的帮助。

干杯

Answer 1

我写了一个算法，可能有点乱，但我认为它确实有效。您的问题陈述并不是100%明确的，因此该解决方案假设您想要选择容器，以便在从最大的容器开始填充时将剩余空间最小化。

// List of cartons
var cartons = new List<double>
{
0.12,
0.09,
0.05
};
// Amount of stuff that you want to put into cartons
var stuff = 0.32;
var distribution = new Dictionary<double, int>();
// For this algorithm, I want to sort by descending first.
cartons = cartons.OrderByDescending(x => x).ToList();
foreach (var carton in cartons)
{
var count = 0;
while (stuff >= 0)
{
if (stuff >= carton)
{
// If the amount of stuff bigger than the carton size, we use carton size, then update stuff
count++;
stuff = stuff - carton;
distribution.CreateNewOrUpdateExisting(carton, 1);
}
else
{
// Otherwise, among remaining cartons we pick the ones that will have empty space if the remaining stuff is put in
var partial = cartons.Where(x => x - stuff >= 0 && x != carton);
if (partial != null && partial.Count() > 0)
{
var min = partial.Min();
if (min > 0)
{
distribution.CreateNewOrUpdateExisting(min, 1);
stuff = stuff - min;
}
}
else
{
break;
}
}
}

有一个附带的扩展方法，它可以向字典中添加一个项，或者如果存在Key，则递增Value。

public static class DictionaryExtensions
{
public static void CreateNewOrUpdateExisting(this IDictionary<double, int> map, double key, int value)
{
if (map.ContainsKey(key))
{
map[key]++;
}
else
{
map.Add(key, value);
}
}
}

---

编辑

在初始内容小于最大容器的情况下发现了一个错误，因此更新了代码以修复它。

注释

这可能仍然不是一个100%万无一失的算法，因为我还没有进行广泛的测试。但它应该给你一个如何进行的想法。

编辑编辑

将条件更改为while (stuff > 0)应该可以修复注释中提到的错误。