تحقق مما إذا كان مجموعة يطابق مجموعة معينة

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");

أحتاج إلى الإجابة على السؤال التالي: إذا كان لدي مستخدمان بحاجة إلى ماسح ضوئي ، ولدي ثلاثة مستخدمين يحتاجون إلى طابعة ، فهل يتناسبون مع غرفة الكمبيوتر الخاصة بي أم لا؟

لا يعمل مبلغ بسيط من جميع الخصائص ، لأنه إذا وضعت ثلاثة أشخاص في الغرفة يحتاجون إلى طابعة ، فلن يكون هناك أي مكان عمل للرجل الفقير الذي يحتاج إلى الماسح الضوئي.

لقد فكرت بالفعل في التكرار من خلال جميع المجموعات الممكنة ، ولكن كلما زاد عدد أماكن العمل ، كلما استغرق الأمر وقتًا أطول وربما يستغرق إكماله إلى الأبد.

Answer 1

عندما قرأت هذا لأول مرة ، كانت رائحتها مثل مشكلة NP-Complete --- وما زالت لديها تلك الرائحة.

لكني أحب إجابة ólafur Waage.

إذا أخذت المستخدمين واحدًا في كل مرة ، فيمكنك حل المشكلة. IE وضع أول مستخدم يصل إلى محطة العمل التي تحتوي على ما يحتاجون إليه فقط ، أو إذا لم يكن هناك ملاءمة-أي المستخدم التالي "يحتاج إلى طابعة ولكن محطة العمل الوحيدة المتبقية مع طابعة تحتوي بالفعل على ماسح ضوئي" ، ثم اذهب إلى الأمام ووضعهم في محطة العمل مع الطابعة والماسح الضوئي.

إذا لم يكن هذا ما تريده-إذا كنت في الواقع ، فأنت تخطط يومًا ما للمستخدمين الذين سيستخدمون الغرفة طوال اليوم ، وما تريد معرفته "ممكنًا أم لا"-ثم أنا "د يقترح عليك إلقاء نظرة على http://en.wikipedia.org/wiki/np-complete قبل قضاء الكثير من الوقت في هذا.

Answer 2

ماذا لو أضفت ما يحتاجون إليه بعد ذلك ، لذلك عندما تضيف شخص 1 إلى الغرفة. ترى أنه يحتاج إلى طابعة ، يمكنك إضافة طابعة إلى مجموعة جديدة من الأشخاص داخل الغرفة وما لديهم حاليًا.

لذلك عند إضافة شخص جديد ، يمكنك التحقق من الوضع الحالي ، وليس حاجة الأشخاص.

Answer 3

أنت تتحدث عن مجموعات متعددة ، وليس مجموعات واضحة. على أي حال ، إذا ، كما في المثال الوحيد الذي تقدمه ، يحتاج الجميع في الغرفة إلى مورد واحد ، وفقط مسألة للموارد ، فإن الحياة سهلة بشكل لا يصدق: فرز مجموعة المعدات الخاصة بك عن طريق الثراء (الماسح الضوئي فقط ، الطابعة فقط ، كلاهما- إدخالات لا تهم!) ، ، قم بتعيين أكبر عدد من الموارد الواحدة فقط مثل Min (متاح ، مطلوب) لكل مورد (وإزالة المطلبين المقابلين) ، الإجابة هي أخيرًا "نعم" إذا كان عدد "كلاهما-- الموارد "المعدات المتبقية هي> = عدد المطلبين المتبقيين.

إذا تمكنت من تحديد فئات المشكلات التي تريد حلها بشكل أكثر وضوحًا ، فيمكن أن تكون الإجابة شحنة وفقًا لذلك (بدون أي قيود ، فستكون بالتأكيد مشكلة مكتملة NP ، كما اقترح إجابة أخرى-ولكن ، يمكن أن تجعل القيود الكافية من الناحية الحسابية قابليه!).