私は、ビンパッキングのバリエーションである問題に取り組んでいますが、追加の制約があるもう少し一般的な形式です。問題の定義は次のとおりです。
オブジェクト クラスにグループ化できるさまざまなサイズのオブジェクトがあります。異なる容量のビンがあり、これらもビン クラスにグループ化されています (同じクラス内のすべてのビンは同じ容量です)。オブジェクト クラスには、配置できるビンに関する制約があります。たとえば、クラス「A」のオブジェクトは、ビン クラス「X」または「Y」のいずれかに配置できます。目的は、オブジェクトの特定のセットの最適なパッキングを生成できる、各クラスのビンの最小数を見つけることです。
この問題の適切な数学的定式化と、あなたが見つけた解決方法はありますか? これは、同じ方法を適用できるビンパッキング問題の拡張ですか? NPハードなのはわかります。問題に取り組む方法について多くを見つけることができなかったので、正しい方向に向けていただければ非常に助かります.
正確な解を見つけることは NP 困難です。しかし、最適解を見つけるのは簡単です。
目的は各クラスのビンの数を最小限に抑えることなので、次のようにします。
入力制約から、各ビン クラスがパックできるオブジェクト クラスを格納する Map を生成します。たとえば、「クラス 'A' のオブジェクトは、ビン クラス 'X' または 'Y' のいずれかに配置できます。」
M[X] = {A};
M[Y] = {A};
すべての制約を処理して、このマップを生成します。ここで、最小数のオブジェクトを持つ bin クラスから開始し、そのクラスへのパッキングを開始し、オブジェクトを Packed[Object_A] = true; としてマークします。
次に、マップ内のビン クラスに対して、カウントの降順で上記の手順を繰り返します。
この後、制約のないオブジェクトと、0 個以上のオブジェクトを持つビン クラスが残ります。
この部分を解決するために、First Fit アルゴリズムを拡張できます。オブジェクト数に基づいてビン クラスを昇順に並べ替えます。残りのオブジェクトでループを実行して、First Fit ビン クラスに入れます。各反復では、オブジェクト数に基づいてビン クラスを並べ替える必要があります。
お役に立てば幸いです。