我正在研究一个问题，它是装箱的一种变体，但有一些更一般的形式，有额外的限制。问题定义如下——
我们有不同大小的对象，可以将它们分组到对象类中。我们有容量不同的垃圾箱，它们也被分为垃圾箱类（同一类中的所有垃圾箱都具有相同的容量）。对象类对它们可以放入哪些箱有限制——例如，“A”类的对象可以放置在“X”或“Y”类中的任何一个中。目标是找到每个类中的最小箱数，这可以产生给定对象集的最佳包装。
这个问题是否有一个很好的数学公式，以及您遇到的解决方法？这是可以应用相同方法的装箱问题的扩展吗？我知道这很难 NP。我找不到太多关于如何解决这个问题的信息，所以如果你能指出我正确的方向，那将非常有帮助。
找到确切的解决方案是 NP 难的。但是找到最佳解决方案很容易。
由于目标是最小化每个班级的垃圾箱数量，我会做这样的事情。
从输入约束生成一个 Map，其中存储每个 bin 类可以打包的对象类。例如，对于约束“'A' 类的对象可以放置在 bin 类 'X' 或 'Y' 中。”
M[X] = {A};
M[Y] = {A};
通过处理所有约束来生成此地图。现在从具有最少对象数量的 bin 类开始并开始打包到其中并将对象标记为 Packed[Object_A] = true;
现在对地图中的 bin 类按照计数的递减顺序重复上述步骤。
在此之后，您将得到没有约束的对象和具有零个或多个对象的 bin 类。
我们可以扩展 First Fit 算法来解决这部分问题。根据其中的对象计数按升序对 bin 类进行排序。在左侧对象上运行循环以放入 First Fit bin 类。在每次迭代中，您需要根据对象计数重新排序 bin 类。
我希望它有所帮助。
目标是找到每个类中的最小箱数
这是一个负载平衡（或公平）约束。诀窍是总计每个类的垃圾箱数量并惩罚该数字的平方：
这样，您不必采用每个班级的平均垃圾箱数：如果另一个硬约束阻止您达到特定班级的平均值，那么这种方式就会崩溃。