在一个项目上工作我遇到了这个问题，我将在问题的真正领域之外进行重新讨论（我想我可以谈论烟花和形状的口径，但它会使理解更加复杂化） . 我正在寻找一种（可能是近似的）算法来解决它 .
我有n个不同大小的容器，m个具有不同大小职业和不同颜色的对象（对象可以是多色的，因此对象的颜色确实是一组） .
我的目标是将所有物体装入容器中（我已经知道这是可能的），这样每个容器的颜色种类最少 . 随着“各种颜色的最小化”，我的意思是每个容器的不同颜色数量的总和是最小的 .
一个例子 . 我有两个大小为2的容器和四个对象，其颜色为，{red，green}，，{blue，green}，每个大小为1.最佳解决方案是[，{red，green}]，[，{blue，green}]，其中总品种为2 2 = 4 . 更糟糕的解决方案是[，]，[{red，green}，{blue，green}]，其中总种类为2 3 = 5 .
我的猜测是问题是NP难，因为它听起来比背包问题更困难：对象的值转换为负值，而且还取决于同一容器内的其他对象 . 但我不知道如何解决近似解决方案的问题，这无论如何都会受到欢迎 .
1 回答
Bin-packing还是背包？
与背包问题相比，这个问题似乎与bin-packing problem有更多共同之处 . 在knapsack problem中，你只需要一个背包来填充，但它有一个你不能超过的容量 . 并且您必须在最大化您选择放入的项目的总 Value 的同时执行此操作 . 此处，您不必耗尽所有项目 .
但是，在装箱问题中，您有多个容器，每个容器都有容量 . 您有兴趣在将每个物品装入某个箱子时尽量减少箱子的数量 . 您还必须尊重每个bin的容量限制 . 与背包不同，在这里你必须用完所有物品 .
在你的情况下，你也试图减少垃圾箱的数量，只有它们不能容纳少于两个 . 而且你也想要用完所有对象 . 你没有多说容量约束，但我假设你也必须尊重它 . 到目前为止，它看起来非常像垃圾箱包装问题 . 您还有一个额外的约束：最小化每个容器中的颜色数 .
NP-hard？
现在，我开始分享你对NP难的预感 - 它拥有bin-packing和一个额外约束的所有元素 . 通过使用所有颜色为红色的对象的实例，可以很容易地显示减少垃圾箱包装 . 我们只需要在NP中显示问题 - 即我们可以在多项式时间内验证结果 . 你去了，我们有一个非正式的证据！
贪心启发式I
这是一个可能有帮助的贪婪启发式 .
表示：不考虑使用集合，而是考虑长度为k的位序列，其中k是您拥有的不同颜色的数量 . 所以，说你有3种颜色 - 红色，绿色，蓝色 . 您将[蓝色] 001，[绿色，蓝色]表示为011，[红色]表示为100等 .
使用比较函数按颜色位序列对项目进行排序，该比较函数产生诸如001,010,100,011,110,111之类的排序 . 您可以设计这样的比较函数作为比特序列的Hamming weight的加权函数及其实际数值 .
请注意，许多颜色模式（位序列）最有可能被许多对象共享 . 这些对象将在排序列表中显示为连续对象 .
遍历排序列表，将相同颜色模式的连续项目分配给同一个bin . 你会从单色到多色项 .
你继续这样，直到你耗尽每个垃圾箱的容量 .
贪心启发式II
另一种方法是以相反的顺序开始填充箱 . 从具有最大颜色数量的对象开始 . 如果它们可以适合，再次将连续对象填充到同一个bin中 . 当你到达颜色较少的项目时，将它们装入已经覆盖了这种颜色的现有垃圾箱中 .
结论
这两种方法都不是最优的，但是嘿，我们不知道吗？我们刚刚勾画了草图非正式的证明，问题是NP难 .
祝好运！