algorithm - パッキング問題

Question

私は次の問題を抱えています：

1. 色の異なる同じ形のアイテムがいくつもあります（各色からいくつあるかわかります）
2. これらのアイテムを、最小数のボックスを使用するように、指定された数（n）のアイテムをそれぞれ保持できるボックスにパックします。round_up（total_nr_of_items / n）
3. 理想的な箱の数がない場合を除いて、1つの箱に入れることができない色がいくつかあります。
4. 箱に入れることができるのは、各色のアイテム（色ごとに異なります）の最小数です。つまり、私は0個を置くことに決めることができます。ボックスまたは最低k個の色の。以上。最小数のボックスで梱包を行うことができなかった場合も、この制約を（可能な限り数回）破ることができます。
5. できるだけ少ない色をボックスに分割する解決策を見つけたいと思います。

これは一種のパッキング問題だと思いますが、どれかわかりません。

上記をどのパッキング問題に変換できるか、および/またはこの問題を解決するために使用できるアルゴリズムを提案してください。

Answer 1

NP-Hard制約充足問題のように見えます。このようなハード制約とソフト制約があります。

組み込みの制約:

• 色の異なる同じ形状のアイテムが一定数あります (各色のアイテムがいくつあるかはわかっています)。

ハード制約:

• 1箱にお入れできない色もございます。

• ボックスに入れることができる各色 (各色によって異なります) の最小数のアイテムがあります。つまり、0 個を配置することができます。ボックスまたは最小k個に色を入れます。以上。

ソフト制約:

• これらのアイテムを、指定された数 (n) のアイテムをそれぞれ保持できるボックスに詰めて、最小数のボックスを使用するようにします: round_up(total_nr_of_items/n)

よりソフトなコンストレイン (または非常に軽量なソフト コンストレイン):

• ボックス間で分割される色をできるだけ少なくするソリューションを見つけたいと考えています。

これを解決するアルゴリズムについては、シミュレーテッド アニーリング、タブー検索、分岐限定などをご覧ください。

このようなアルゴリズムを実装し、制約をサポートするソフトウェアについては、Drools Planner (Java、オープン ソース) を参照してください。

Answer 2

これは NP-Hard である可能性があります。

パーティションの問題 (正の整数の場合) はそれに帰着するようです。

正の整数の配列 A[1,...n] が与えられた場合、そのうちのいくつかのサブセットを見つける必要がありますが、その和はその補数と同じです。

色は 1 から n であると考えてください。2 つのボックスがあります。色 i に対してボックスが保持できる最小値は A[i] であり、色 i のアイテムは正確に A[i] 個あります。

各ボックスに保持できるアイテムの最大数は (A[1] + .. + A[n])/2 です。