Проверьте, соответствует ли комбинация данному набору - PullRequest
Новая
       53

Проверьте, соответствует ли комбинация данному набору

0 голосов
/ 18 ноября 2009

В основном я ищу решение, которое возвращает, если данная комбинация соответствует заданному набору.

Пример: у меня есть массив, в котором хранится информация о том, какое компьютерное помещение и какое рабочее место имеет какое оборудование. Мне нужно выяснить, может ли данное количество пользователей с особыми потребностями вписаться в компьютерную комнату или нет. Индекс - это номер рабочего места в моем примере. 

$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 ]

0 голосов
/ 18 ноября 2009

Когда я впервые прочитал это, оно пахло проблемой NP-завершения - и у него все еще есть этот аромат.

Но мне нравится ответ Олафура Вейджа.

Если вы принимаете пользователей по одному, то вы можете решить проблему. то есть поставить первого пользователя, который прибудет на рабочую станцию, которая имеет именно то, что ему нужно, или, если она не подходит, т.е. следующему пользователю «нужен принтер, но единственная рабочая станция, на которой остался принтер, уже имеет сканер», а затем отправьте их на рабочую станцию ​​с принтером и сканером.

Если это не то, что вы хотите - если действительно, вы планируете на один день раньше пользователей, которые будут использовать комнату в течение всего дня, и вы хотите знать, "выполнимо или нет" -Тогда я бы посоветовал вам взглянуть на http://en.wikipedia.org/wiki/NP-complete, прежде чем тратить на это слишком много времени.

0 голосов
/ 18 ноября 2009

Вы говорите о мультимножествах, а не простых наборах. В любом случае, если, как в приведенном вами единственном примере, всем в комнате нужен один ресурс, а важны только два ресурса, жизнь невероятно проста: отсортируйте массив оборудования по богатству (только сканер, только принтер, оба - записи, предлагающие ни то, ни другое, не имеют значения!), назначают столько же однресурсных ресурсов, сколько min (доступно, запрошено) для каждого ресурса (и удаляют соответствующие запросчики), в конце концов, ответ «да», если число «обоих «осталось ресурсов оборудования»> = количество оставшихся запросчиков.

Если вы можете более четко указать, какие классы задач вы хотите решить, ответ можно соответствующим образом отточить (без каких-либо ограничений это определенно будет NP-полной задачей, как предложил другой ответ - но достаточно ограничений может сделать это вычислительно выполнимым!).

0 голосов
/ 18 ноября 2009

Как насчет того, если вы добавите то, что им нужно, потом, когда вы добавите человека 1 в комнату. Вы видите, что ему нужен принтер, вы добавляете принтер в новый массив людей в комнате и то, что у них есть в данный момент.

Поэтому, когда вы добавляете нового человека, вы проверяете текущий статус, а не потребности людей.

...