我正在研究一個問題，這是一個變形的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類進行重新排序。
我希望它有幫助。
目的是找到在每個類
這是一個負載均衡（或公平性）約束的二進制位的最小數目。訣竅是總每班倉的數量和懲處數的平方：
這樣，你不必採取每班箱的平均數：這種方式分解如果另一個硬約束阻止你達到某個特定課程的平均水平。