# Approach to algorithm for assignment of resources

We have a requirement to be able to match people with locations based on availability and certain conditions.

Let's say I have a group of people each with 3 types of things they may need to park. A car, a truck and a boat. Each person also indicates their preferred parking location (choices 1, 2 and 3).

I also have a list of parking locations which can handle a certain number of each of those things. The goal is to match everyone up so that we maximum usage. The main requirement is that each individual person has to be able to park everything in the same location OR they don't get to park at all.

Example:
Starting with the parking locations I have:

``````Lot    Cars    Trucks    Boats
A       2       0         2
B       2       1         3
C       0       5         0
``````

For people I have:

``````Person    Cars    Trucks    Boats    Choice 1  Choice 2  Choice 3
Tom        2       1         0         A         B         C
Betty      1       0         1         B         C         A
Sam        0       2         0         C         A         B
Pat        3       2         1         A         C         B
``````

My initial thought is to simply sort the people by the number of items they have (largest to smallest). Then attempt to place each one based on choice. IE: I'd try to place Pat first (most items), but couldn't because no lot meets the requirements. Then I'd try Tom, who would go into Lot B. Etc.

Do you know of any issues with that approach?

Bonus points: is there a name for this type of problem?

• Subset-Sum or Knapsack? – JeffO Nov 22 '13 at 20:41

It's not quite that simple. You'd have to do backtracking in the cases where one person matches multiple lots. Let's say you have the same lots, but the following people:

``````Person    Cars    Trucks    Boats    Choice 1  Choice 2  Choice 3
Adam       2       0         1         B         A         C
Eve        1       1         0         B         C         A
``````

Adam could fit into `B` or `A`, so you let him have his first choice: `B`. Now Eve can't fit anywhere, even though if Adam was in `A`, she could fit in `B`. So you need a means of backtracking to make a different choice for Adam. It's also possible for the ideal solution to not allow someone with the largest request, even if they fit, so you need to take that into account as well.

I don't know if there's a well-known name for this exact problem. The most common name I see for the general problem is "resource allocation."

This seems like a variant of the Knapsack problem however instead of having a single bag you have several and each item has a preference about which bag it belongs to. Consult your local Computer Science department for confirmation.

If it is a Knapsack problem variant then you're into NP-Complete territory in terms of complexity. Which means pragmatically you're looking at an optimisation problem, so find the solution that is as close to optimal as possible.

``````Create a list of Lots lots.