接近背包问题？

Question

我认为我试图解决的问题有点类似于背包问题。不过，我不太确定。

请看下面的输入和我的解决方案。有三种类型的项目和4个桶。问题是在4个桶中尽可能保持项目的一致性。也就是说，桶的容量(或桶中物品的数量)应该相等(或接近相等)。您还可以将来自不同类型的项目保存在同一个桶中。

示例输入：

item-type   :   A   B   C
  #items    :   12  36  25

我目前使用的一个简单解决方案如下：

1. 因为有4个桶，所以每个桶都应该得到(sum of items)/4。对于上面的示例输入数据，它是(12 + 36 + 25)/4，即大约18项。每个桶的容量应该“接近”到18。
2. 然后开始把A型的物品保存到第一个桶中，直到第一个桶的数量变成18个为止。但是，由于A类物品的数量是12，我们仍然需要6个项目。因此，将B型的6个项目保留到第一个桶中，这样第一个桶的容量就可以达到18个。就像这样，其他三个水桶也会被填满。

最后，四个桶如下：

Bucket-1: (12 A items, 6 B items)
Bucket-2: (18 B items)
Bucket-3: (12 B items, 6 C items)
Bucket-4: (19 C items).

我认为这个问题的时间复杂度是O(N^2)，N是桶数。

如果有人能帮助我进一步改进解决方案，那就太好了。

注-1:我们可以在同一个桶中混合不同类型的物品。

注2:我们还需要将物品类型的信息保存在桶中。

Answer 1

看起来，您所有的项目都有相同的大小，在这种情况下，解决方案是微不足道的。数数项目的总数，假设这个数字是c，比如说有n个桶。计算x=地板(c / n)和y=c*x，然后y桶装满x+1项，n-y桶装满x项。

为了使这成为一个有趣的问题，假设不同的项目类型有不同的大小，并假设这一次所有权重的总和为c。在这种情况下，您很可能无法将项目分配到重量为x和x+1的箱子中，或者很难这样做。如果这是不可能的，那么您需要定义什么是“最佳”解决方案。

Answer 2

对于项目数量A、B、C和桶数量N，每一桶应分别保持接近A/N + B/N + C/N项目。实际放置项目应采取O(N)。

您可以使用循环选择在桶中分配A mod N+B mod N+C mod N项目:将A类型的剩余项放入第1桶，将B类型的剩余项放入桶#2，等等，根据需要将其包装到第1桶。一个巧妙的使用mod运算符，也应该使这个O(N)。

Answer 3

你不想迭代总项目的数量而不是桶^2吗？

例如,

item[0] goes into bucket 1.
item[1] goes into bucket 2.
item[2] goes into bucket 3.
item[3] goes into bucket 4.
item[4] goes into bucket 1.

需要考虑的是:每个项目是否都有一个属性，项目类型作为其定义的一部分？例如，你知道一个红色的大理石，是红色的。物品分类了吗？