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

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-полная задача - и у нее до сих пор есть этот аромат.

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

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

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

Answer 2

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

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

Answer 3

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

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