如何在桶中分配多个元素，使其在一个范围内？

Question

我有50个元素n1、n2、n3、.、n50和有限数量的桶，比如5个桶和每个桶可以容纳一个范围从100到150 (这只不过是那个桶中元素的总和)，但不少于100个，也不超过150个。

哪一种算法最适合解决这个问题，例如所有的5个桶和所有元素(n1，n2，n3，.)也用完了吗？

如果不能使用桶，或者必须省略任何元素，则该算法应该只返回"InvalidConditionsFound“。

我试过背包，它给你的组合接近一个给定的数字，但如何使它在一个范围内，并确保它明智地选择这样所有的桶都装满了，而不是两个桶得到150满，而另一个桶只在，比如说50？

Answer 1

50个元素x5个桶？这些都是小数目。一种蛮力的回溯启发可能会奏效。对它们进行排序，将元素添加到桶中，以使桶总数保持相等。如果你不能一次得到解决办法，那就后退一步。

我曾经用过一个类似的过程，把货盘分配给卡车。目标是尽量减少装载所有托盘所需的卡车数量。每辆卡车都有一个最大的重量能力(和托盘限制)。首先，我遵循最佳匹配-首先装载理论最低数量的卡车。如果我还剩下托盘的话，我找到了两辆最空的卡车，并做了一次蛮力的重新包装，看我能否再挤进一个托盘。该算法成功地将200个总重量为499,000磅的托盘装入10辆载重量为50,000磅的卡车中。

Answer 2

您有K桶，目前是五个。

对您的正输入值进行排序，并找到它们的和，s。验证是否为100 × K ≤ s ≤ 150 × K，或立即中止。

贪婪地处理每个输入值，从最大到最小，并将其分配给一个桶。在算法的一个变体中，决定性地将其分配给当前最轻的桶。在一个更昂贵的变体中，将它随机分配到一个合格的桶中，如果事情一开始不成功，就做好一些回溯或重试的准备。