Avatar of kenpem
kenpem
Flag for United Kingdom of Great Britain and Northern Ireland

asked on 

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

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?
Game ProgrammingDelphiAlgorithms

Avatar of undefined
Last Comment
kenpem

8/22/2022 - Mon