我正在研究一个问题，这是一个变形的bin-packing，但有一个更多的一般形式与额外的约束。问题定义如下 -Bin包装的变化 - 与箱和对象类和相互约束
我们有不同大小的对象，可以将它们组合到对象类中。我们有不同容量的容器，它们也被分为容器类（同一类容器中的所有容器都具有相同容量）。对象类对它们可以放置在哪些容器上具有约束 - 例如，可以将类“A”的对象放置在容器类“X”或“Y”中的任一个中。其目标是找到每个班级的垃圾桶的最小数量，这可以产生一组给定对象的最佳包装。
这个问题是否有一个很好的数学表达式，以及您遇到的解决方法？这是否可以应用相同的方法来解决装箱问题？我明白这是NP难。我无法找到解决问题的方法，所以如果您能指出正确的方向，这将非常有帮助。
找到确切的解决方案是NP-hard。但寻找最佳解决方案非常简单。
由于目标是尽量减少每个班级的垃圾箱数量，我会做这样的事情。
从输入约束生成一个Map，该Map存储每个bin类可以打包的对象类。例如。用于约束“类‘A’的对象可以被放置在任一的bin类‘X’或‘Y’的”。
M[X] = {A};
M[Y] = {A};
通过所有约束生成此图由处理。现在从具有最少数量对象的bin类开始，开始打包并标记对象为 Packed [Object_A] = true;
现在重复上述步骤，以地图中的垃圾桶类别的数量为递减顺序。
在此之后，您将剩下没有约束的对象，并且具有零个或多个对象的bin类。
我们可以扩展First Fit算法来解决这部分。 根据升序中的对象数量对bin类进行排序。在对象左侧运行一个循环，放入First Fit bin类。在每次迭代中，您都需要根据对象计数对bin类进行重新排序。
我希望它有帮助。
目的是找到在每个类
这是一个负载均衡（或公平性）约束的二进制位的最小数目。诀窍是总每班仓的数量和惩处数的平方：
这样，你不必采取每班箱的平均数：这种方式分解如果另一个硬约束阻止你达到某个特定课程的平均水平。