4

在一个项目中我遇到了这个问题，我将在这里用问题的实际领域之外的术语重新表述（我想我可以谈论烟花的口径和形状，但这会使理解更加复杂）。我正在寻找一种（可能是近似的）算法来解决它。

我有n个大小不一的容器，m个不同大小职业、不同颜色的物件（物件可以是多色的，所以一个物件的颜色是真正的一套）。

我的目标是将所有对象放入容器中（我已经知道这是可能的），以便每个容器的颜色种类最小化。对于“颜色的种类被最小化”，我的意思是每个容器的不同颜色数量的总和是最小的。

一个例子。我有两个大小为 2 的容器和四个对象，它们的颜色是 {red}、{red,green}、{blue}、{blue,green}，每个大小为 1。最佳解决方案是 [{red} , {red, green}], [{blue}, {blue, green}]，其中总品种为 2+2=4。更糟糕的解决方案是 [{red}, {blue}], [{red, green}, {blue, green}]，其中总品种为 2+3=5。

我的猜测是这个问题是 NP 难题，因为它听起来比背包问题更难：对象的值被转换为负值，而且取决于同一容器内的其他对象。但是我不知道如何解决这个问题以获得一个近似的解决方案，无论如何这将是非常受欢迎的。

4

1 回答 1

3

装箱还是背包？

这个问题似乎与装箱问题比与背包问题有更多的共同点。在背包问题中，你只有一个背包要装，但它有一个容量，你不能超过。而且您必须在最大化您选择放入的物品的总价值的同时这样做。在这里，您不必用完所有物品。

然而，在装箱问题中，您有多个箱，每个箱都有一个容量。您有兴趣在将每个项目装入某个 bin 的同时最小化 bin 的数量。您还必须尊重每个箱的容量限制。与背包不同，在这里您必须用完所有物品。

在您的情况下，您还试图最小化垃圾箱的数量，但它们不能少于两个。而且您还想用完所有对象。您对容量限制没有说太多，但我假设您也必须尊重这一点。到目前为止，它看起来很像装箱问题。您还有一个额外的限制：尽量减少每个容器中的颜色数量。

NP难？

现在，我开始与您分享关于它是 NP-hard 的预感——它具有 bin-packing 的所有元素和一个额外的约束。通过使用带有所有红色对象的实例，应该很容易显示从装箱中的减少。我们只需要证明NP中的问题——即我们可以在多项式时间内验证结果。你去吧，我们在那里有一个非正式的证明！

贪婪启发式 I

这是一个可能会有所帮助的贪婪启发式方法。

表示：不使用集合，而是考虑长度为k的位序列，其中k是您拥有的不同颜色的数量。所以，假设你有 3 种颜色——红色、绿色、蓝色。您可以将 [blue] 001，[green, blue] 表示为 011，[red] 表示为 100，等等。

  1. 使用比较函数按其颜色位序列对项目进行排序，该比较函数会产生诸如 001、010、100、011、110、111 之类的排序。您可以将此类比较函数设计为 位序列的汉明权重的加权函数及其实际数值。

  2. 请注意，许多颜色模式（位序列）很可能会被许多对象共享。这些对象将在排序列表中显示为连续对象。

  3. 遍历排序列表，将相同颜色模式的连续项目分配给相同的 bin。你会从单色到多色项目。

  4. 您继续这种方式，直到用尽每个垃圾箱的容量。

贪婪启发式 II

另一种方法是开始以相反的顺序填充垃圾箱。从颜色数量最多的对象开始。如果可以的话，再次将连续的对象填充到同一个 bin 中。当您找到颜色较少的物品时，将它们放入已经覆盖该颜色的现有垃圾箱中。

结论

这两种方法都不是最优的，但是，嘿，我们不是已经知道了吗？我们刚刚草拟了一个非正式的证明，这个问题是 NP 难题。

祝你好运！

于 2012-04-21T06:33:46.627 回答