Comprobar si coincide con una combinación de un conjunto dado

Question

Básicamente estoy buscando una solución que devuelve si una combinación dada coincide con un conjunto dado.

Ejemplo: Tengo una matriz que almacena qué ordenador habitación y que lugar de trabajo tiene que equipo. Necesito averiguar si un determinado número de usuarios con necesidades específicas puede caber en la sala de ordenadores o no. El índice es el número de lugares de trabajo en mi ejemplo.

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

Tengo que responder a la siguiente pregunta: ¿Si tengo dos usuarios que necesitan un escáner, y tengo tres usuarios que necesitan una impresora, haga encajan en mi sala de ordenadores o no

?

Una simple suma de todas las propiedades no funciona, ya que si pongo a tres personas en la habitación que necesitan una impresora, no habría ningún lugar de trabajo dejado por el pobre tipo que necesita el escáner.

Ya pensé en iteración a través de todas las combinaciones posibles, pero cuanto mayor sea el número de lugares de trabajo, más tiempo que tomaría y, posiblemente, tener siempre a completar.

Answer 1

Cuando leí por primera vez este, que olía como un problema NP-completo --- y que todavía tiene ese aroma.

Pero me gusta la respuesta de Ólafur Waage.

Si usted toma los usuarios de uno en uno, entonces se puede resolver el problema. es decir, poner el primer usuario para llegar a la estación de trabajo que tiene justo lo que necesitan, o si no hay ningún ajuste --- es decir. el siguiente usuario "necesita una impresora, pero la única estación de trabajo a la izquierda con una impresora ya cuenta con un escáner", a continuación, seguir adelante y poner ellos en la estación de trabajo con la impresora y el escáner.

Si eso no es lo que quiere --- si es que, usted está planeando un día antes para los usuarios que van a utilizar la sala durante todo el día, y lo que quiere saber es "factible o no" --- -entonces te sugiero que eche un vistazo a http://en.wikipedia.org/wiki / NP-completo antes de pasar demasiado tiempo en esto.

Answer 2

¿Qué tal si se agrega lo que necesitan después, así que cuando se agrega 1 persona en la habitación. Usted ve que necesita una impresora, se agrega una impresora en una nueva serie de personas dentro de la habitación y lo que tienen actualmente.

Así que cuando se agrega una nueva persona, comprobar el estado actual, no la necesidad de las personas.

Answer 3

Estamos hablando conjuntos múltiples, no juegos de civil. De todos modos, si, como en el único ejemplo que das, todo el mundo en la habitación necesita un único recurso, y sólo dos cuestiones de recursos, la vida es muy fácil: Ordenar su gama de equipos de riqueza (escáner de sólo, impresora solamente, ambos - que ofrecen entradas ni no importan!), asignar hasta uno de los recursos sólo en min (liviano, solicitada) para cada recurso (y eliminar los solicitantes correspondientes), la respuesta es finalmente "sí" si el número de "ambos- de recursos equipos" izquierda es> = el número de los solicitantes fue.

Si se puede especificar con mayor claridad lo que las clases de problemas que se quieren resolver, la respuesta puede ser afilada en consecuencia (sin ningún tipo de limitaciones, que sin duda será un problema NP-completo, tal como sugiere otra respuesta - pero, suficientes restricciones pueden que sea computacionalmente factible!).