We help IT Professionals succeed at work.
Get Started

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

348 Views
Last Modified: 2013-12-26
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?
Comment
Watch Question
Senior Developer
CERTIFIED EXPERT
Commented:
This problem has been solved!
Unlock 1 Answer and 15 Comments.
See Answer
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE