Verifique se uma combinação corresponde a um determinado conjunto

Question

Basicamente, estou procurando uma solução que retorne se uma determinada combinação corresponde a um determinado conjunto.

Exemplo: eu tenho uma matriz que armazena qual sala de computadores e qual local de trabalho possui qual equipamento. Preciso descobrir se um determinado número de usuários com necessidades específicas pode atender à sala do computador ou não. O índice é o número do local de trabalho no meu exemplo.

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

Preciso responder à seguinte pergunta: Se eu tenho dois usuários que precisam de um scanner e tenho três usuários que precisam de uma impressora, eles se encaixam na minha sala de informática ou não?

Uma soma simples de todas as propriedades não funciona, pois se eu colocar três pessoas na sala que precisam de uma impressora, não haveria um local de trabalho para o pobre rapaz que precisa do scanner.

Eu já pensei em itentar todas as combinações possíveis, mas quanto maior o número de locais de trabalho, mais tempo levaria e possivelmente levaria uma eternidade para concluir.

Answer 1

Quando li isso pela primeira vez, cheirava a um problema completo de NP-e ainda tem esse aroma.

Mas eu gosto da resposta de Ólafur Waage.

Se você levar os usuários um de cada vez, poderá resolver o problema. ou seja, colocou o primeiro usuário a chegar à estação de trabalho que tem exatamente o que eles precisam ou se não há ajuste-ou seja, o próximo usuário "precisa de uma impressora, mas a única estação de trabalho que resta com uma impressora já tem um scanner", depois vá À frente e coloque -os na estação de trabalho com a impressora e o scanner.

Se não é isso que você quer-se, de fato, você está planejando um dia pela frente para os usuários que vão usar a sala durante todo o dia, e o que você quer saber é "viável ou não" ---- então eu 'D sugiro que você dê uma olhada em http://en.wikipedia.org/wiki/NP-Complete Antes de passar muito tempo com isso.

Answer 2

Que tal se você adicionar o que eles precisam depois, então quando você adiciona a pessoa 1 na sala. Você vê que ele precisa de uma impressora, adiciona uma impressora a uma nova variedade de pessoas dentro da sala e o que elas têm atualmente.

Então, quando você adiciona uma nova pessoa, você verifica o status atual, não a necessidade das pessoas.

Answer 3

Você está falando de multisets, não conjuntos simples. De qualquer forma, se, como no único exemplo que você dá, todos na sala precisam de um único recurso, e apenas dois recursos importantes, a vida é incrivelmente fácil: classifique sua matriz de equipamentos por riqueza (somente scanner, somente impressora, ambos- As entradas que não são importantes não importam!), Atribua tantos recursos únicos quanto min (disponível, solicitado) para cada recurso (e remova os solicitadores correspondentes), a resposta finalmente é "sim" se o número de "ambos- Recurso "Equipamentos restantes são> = o número de solicitadores deixados.

Se você pode especificar com mais clareza quais classes de problemas que deseja resolver, a resposta pode ser afiada de acordo (sem restrições, definitivamente será um problema de preenchimento NP, como sugeriu outra resposta-mas restrições suficientes podem torná-lo computacionalmente viável!).