組み合わせは、指定されたセットに一致するかどうかをチェック

Question

基本的に私は、所定の組み合わせが特定のセットと一致した場合に返されます解決策を探しています。

例：私はどのコンピュータルームや職場店舗がどの機器を持つ配列を持っています。私は特定のニーズを持つユーザーの指定した数は、コンピュータ室やないに収まることができるかどうかを確認する必要があります。インデックスは、私の例では、職場の番号です。

$aComputerRoomEquipment = array();
$aComputerRoomEquipment[1] = array("PC");
$aComputerRoomEquipment[2] = array("PC");
$aComputerRoomEquipment[3] = array("PC", "Scanner");
$aComputerRoomEquipment[4] = array("PC", "Printer");
$aComputerRoomEquipment[5] = array("PC", "Scanner", "Printer");
$aComputerRoomEquipment[6] = array("PC");
$aComputerRoomEquipment[7] = array("PC", "Scanner", "Printer");
$aComputerRoomEquipment[8] = array("PC");

私は、次の質問に答える必要があります。私はスキャナを必要とする二人のユーザーを持っている、と私はプリンタを必要とする3人のユーザーを持っている場合、彼らは私のコンピュータルームにか合わない

？

すべてのプロパティの単純合計は動作しません、私はプリンタを必要とする部屋に3人を置く場合は、スキャナを必要とする貧しい男のために残された職場がないからである。

私はすでに、すべての可能な組み合わせを反復処理すると思ったが、職場の数が多いほど、より長く、それが完了するまでに永久に取る可能性が取ると考え、である。

Answer 1

私が最初にこれを読んだとき、

、それはNP完全問題のようなにおいがしました---それはまだその香りを持っています。

しかし、私はオラフルWaageの答えが好きです。

あなたは、ユーザーを一つずつ取る場合は、

、あなたは問題を解決することができます。すなわち、彼らが必要なものだけ持っている、または全くフィット感が存在しない場合は、ワークステーションに到着した最初のユーザー---すなわちを置きます。次のユーザーは、「プリンタを必要としますが、プリンタに残された唯一のワークステーションは、すでにスキャナを持っている」その後、先に行くと、プリンタとスキャナとワークステーションでそれらを置きます、。

それはあなたが望むものではない場合---確かならば---、あなたは全体の日のために部屋を使用しようとしているユーザーのために先に一日を計画している、とあなたが知りたいことは、「実現可能かどうか」であります私はあなたが http://en.wikipedia.org/wikiを見てお勧めしたい-thenこの上であまりにも多くの時間を費やす前に/ NP-完全に。

Answer 2

どのようにあなたがそうあなたが部屋の中に人の1を追加するとき、彼らはその後必要なものを追加した場合について。あなたは部屋の中の人々と彼らが現在持っているの新しい配列にプリンタを追加し、彼はプリンタが必要であることがわかります。

あなたは新しい人を追加するとき、

だから、あなたは現在の状態ではなく、人々の必要性を確認します。

Answer 3

あなたはマルチセットではなく、プレーンなセットを話しています。とにかく、あれば、あなたが与える唯一の例のように、部屋に誰もが単一のリソースを必要とし、唯一の2つのリソースの問題は、生活は非常に簡単です：ソートお使いの装置の配列を豊かで（スキャナのみ、プリンタのみ、両方 - 提供でもないエントリは重要ではありません！）、）リソースごとに）要求し、（のavailble分と同じ数の一のリソースのみの割り当て（および対応する要求元を削除し、答えは「はい」「both-の数であれば、最終的です左リソース」機器は> =リクエスタの数が残っている。

しかし、十分な制約がすることができます - あなたがより明確にあなたが解決したい問題のどのクラスを指定することができた場合は、

、答えは別の答えが示唆されているように任意の制約を受けることなく、それは間違いなく、NP完全問題になります（それに応じてシャープにすることができますそれは計算上実現可能に！）。