troubleshooting Question

How to do best-match allocation of items to customers?

Avatar of kenpem
kenpemFlag for United Kingdom of Great Britain and Northern Ireland asked on
Game ProgrammingDelphiAlgorithms
15 Comments1 Solution349 ViewsLast Modified:
This is perhaps best explained by an illustrative example rather than in terms of coding requirements:

Imagine I'm running a lending library. Not quite a typical library, as you'll see.Customers have supplied lists of the books they'd like to borrow, and indicated how important each book is. I obviously have a list of what stock I have available, and stock is limited - there is never enough on hand to completely satisfy all customers. Customers can have two books at a time.

Tim's list contains, in his order of preference:
Book A
Book B
Book C
Book D
Book E

John's list contains:
Book A
Book B

And I have one copy of each book in stock. Obviously if I send Tim his top two choices, John won't get anything, but this is easily and visibly solvable in this example - send John his top two, and Tim gets C and D. Everybody got something, and where possible they got the best possible pick. Now add three more people and ten more books into the equation and it quickly gets a lot more complex.

How would I go about developing a reasonably intelligent best-match algorythm? The obvious solution would be to simply try every possible permutation and select the result set with the most books allocated and the highest choices from each list. But that soon becomes ridiculous as the numbers ramp up, as every person/book added doubles the number of possible outcomes.

Is there a standard way of doing something like this?
ASKER CERTIFIED SOLUTION
TheRealLoki
Senior Developer

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 1 Answer and 15 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 15 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros