algorithm - 最小化颜色 : a variation of the knapsack algorithm?

Question

在做一个项目时我遇到了这个问题，我将在这个问题的实际领域之外重新措辞(我想我可以谈论烟花的口径和形状，但这会使理解更加复杂).我正在寻找一种(可能是近似的)算法来解决它。

我有 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 难的，因为它听起来比背包问题更难:对象的值被转换为负值，而且还取决于同一容器内的其他对象。但是我不知道如何解决近似解决方案的问题，无论如何这将是非常受欢迎的。

Answer 1

装箱还是背包？

这个问题似乎与 bin-packing problem 有更多共同点而不是背包问题。在knapsack problem ，你只有一个背包可以装满，但它有一个你不能超过的容量。并且您必须在最大化您选择放入的元素的总值(value)的同时做到这一点。在这里，您不必用完所有元素。

但是，在装箱问题中，您有多个箱子，每个箱子都有一个容量。您有兴趣在将每件元素放入某个箱子时尽量减少箱子的数量。您还必须遵守每个箱子的容量限制。与背包不同，在这里您必须用完所有元素。

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

NP难？

现在，我开始与您分享关于它是 NP-hard 的预感——它具有装箱的所有元素和一个额外的约束。比方说，通过使用一个对象全部为红色的实例，可以很容易地显示从装箱中减少的情况。我们只需要证明 NP 中的问题——即我们可以在多项式时间内验证结果。好了，我们有一个非正式的证明!

贪心启发式 I

这里有一个可能有用的贪心启发法。

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

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

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

3. 遍历排序列表，将具有相同颜色模式的连续项目分配到同一容器。您将从单色变为多色商品。

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

贪心启发式 II

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

结论

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

祝你好运!