Question

Basically I m looking for a solution which returns if a given combination matches a given set.

Example: I have an array which stores which computer room and which workplace has which equipment. I need to find out if a given number of users with specific needs can fit into the computer room or not. The index is the workplace number in my example.

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

I need to answer the following question: If i have two users who need a scanner, and i have three users who need a printer, do they fit into my computer room or not?

A simple sum of all properties doesn t work, since if I put three people in the room who need a printer, there wouldn t be any workplace left for the poor guy who needs the scanner.

I already thought of iterating through all possible combinations, but the larger the number of workplaces is, the longer it would take and possibly take forever to complete.

Answer 1

When I first read this, it smelled like an NP-complete problem---and it still has that aroma.

But I like Ólafur Waage s answer.

If you take the users one at a time, then you can solve the problem. i.e. put the first user to arrive at the workstation that has just what they need, or if there is no fit---i.e. the next user "needs a printer but the only workstation left with a printer already has a scanner", then go ahead and put them at the workstation with the printer and the scanner.

If that s not what you want---if indeed, you are planning one day ahead for users that are going to use the room for the entire day, and what you want to know is "feasible or not"----then I d suggest you take a look at http://en.wikipedia.org/wiki/NP-complete before spending too much time on this.

Answer 2

How about if you add what they need afterwards, so when you add person 1 into the room. You see that he needs a printer, you add a printer into a new array of people within the room and what they currently have.

So when you add a new person, you check the current status, not the need of the people.

Answer 3

You re talking multisets, not plain sets. Anyway, if, as in the only example you give, everybody in the room needs a single resource, and only two resources matters, life is incredibly easy: sort your equipment array by richness (scanner-only, printer-only, both -- entries offering neither don t matter!), assign as many one-resources-only as min(availble, requested) for each resource (and remove the corresponding requestors), the answer is finally "yes" if the number of "both-resource" equipments left is >= the number of requestors left.

If you can specify more clearly what classes of problems you want to solve, the answer can be sharpened accordingly (without any constraints, it will definitely be a NP-complete problem, as another answer suggested -- but, enough constraints can make it computationally feasible!).

友情链接