Vérifiez si une combinaison correspond à un ensemble donné

Question

En fait, je suis à la recherche d'une solution qui retourne si une combinaison donnée correspond à un ensemble donné.

Exemple: J'ai un tableau qui stocke qui place l'ordinateur et qui a lieu de travail quel équipement. Je dois savoir si un certain nombre d'utilisateurs ayant des besoins spécifiques peut entrer dans la salle informatique ou non. L'indice est le numéro de travail dans mon exemple.

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

je dois répondre à la question suivante: Si j'ai deux utilisateurs qui ont besoin d'un scanner, et j'ai trois utilisateurs qui ont besoin d'une imprimante, intègrent-ils dans ma chambre d'ordinateur ou pas

?

Une simple somme de toutes les propriétés ne fonctionne pas, car si je mets trois personnes dans la salle qui ont besoin d'une imprimante, il n'y aurait pas de lieu de travail pour le reste pauvre gars qui a besoin du scanner.

Je l'ai déjà pensé à itérer toutes les combinaisons possibles, mais plus le nombre de lieux de travail est, plus il faudrait et peut-être prendre une éternité pour terminer.

Answer 1

Quand je lis cela, ça sentait comme un problème NP-complet --- et il a encore que l'arôme.

Mais j'aime la réponse de Ólafur Waage.

Si vous prenez les utilisateurs un à la fois, alors vous pouvez résoudre le problème. à savoir mettre le premier utilisateur pour arriver au poste de travail qui a tout ce dont ils ont besoin, ou s'il n'y a pas en forme --- i.e.. l'utilisateur suivant « a besoin d'une imprimante, mais le seul poste de travail à gauche avec une imprimante dispose déjà d'un scanner », alors allez-y et les mettre à la station de travail avec l'imprimante et le scanner.

Si ce n'est pas ce que vous voulez --- si bien, vous prévoyez un jour d'avance pour les utilisateurs qui vont utiliser la salle pour toute la journée, et ce que vous voulez savoir est « faisable ou non » --- -Alors je vous suggère de jeter un oeil à http://en.wikipedia.org/wiki / NP-complet avant de passer trop de temps à ce sujet.

Answer 2

Que diriez-vous si vous ajoutez ce dont ils ont besoin par la suite, donc quand vous ajoutez 1 personne dans la pièce. Vous voyez qu'il a besoin d'une imprimante, vous ajoutez une imprimante dans un nouveau tableau de personnes dans la salle et ce qu'ils ont actuellement.

Alors, quand vous ajoutez une nouvelle personne, vous vérifiez l'état actuel, pas le besoin du peuple.

Answer 3

Vous parlez multijeux, pas de jeux simples. Quoi qu'il en soit, si, comme dans le seul exemple que vous donnez, tout le monde dans la salle a besoin d'une seule ressource, et seulement deux questions de ressources, la vie est incroyablement facile: trier votre tableau d'équipement par la richesse (scanner uniquement, imprimante seule, à la fois - entrées offrant ni ne comptent pas!), attribuer autant une-ressources seulement comme min (availble, demandé) pour chaque ressource (et supprimer les correspondants demandeurs), la réponse est enfin « oui » si le nombre de « deux- ressources » équipements gauche est> = le nombre de gauche demandeurs.

Si vous pouvez indiquer plus clairement quelles catégories de problèmes que vous voulez résoudre, la réponse peut être affûtée en conséquence (sans aucune contrainte, il sera certainement un problème NP-complet, comme une autre réponse suggérée - mais, assez de contraintes peut rendre possible informatiquement!).