1
$\begingroup$

We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We want to maximize the number of people who receive all the items on their list. The inventory may not have enough items to satisfy all the wishes.

To give an example:
Alice - wants: 1 apple
Bob - wants: 3 bananas, 1 cherry
Charlie - wants: 2 apples, 1 banana

Inventory: 1 apple, 3 bananas, 2 cherries

One optimal solution is:
Alice - gets: 1 apple
Bob - gets: 3 bananas, 1 cherry
Charlie - gets: 1 cherry

Alice and Bob are satisfied, and it doesn't matter what Charlie gets.

Here is what I tried so far:
I tried searching for a similar problem, but the only thing I could find are variations of the assignment problem, or the matching problem, all of which do not quite match the one at hand. I don't think the assignment problem applies, because it has a cost function for each assignment, which is independent of the other assignments, but here we have global cost function. We could model the situation similar to a matching problem where we would have a bipartiate graph of vertices one side being the people and the other being the items with edges representing the wishes (we could have multiple edges for a pair of person and item to represent the amount) and have a "capacity" on each item to represent the inventory. Then we could find some sort of matching which satisfies the constraints. But I am not sure which algorithm could be used for that.

$\endgroup$
1
  • $\begingroup$ this reminds me of the scene in the movie "the beautiful mind" where John Nash came up with the equilibrium theory to get everyone get laid $\endgroup$
    – B.Mr.W.
    Jan 4, 2023 at 1:49

1 Answer 1

1
$\begingroup$

In the special case where the inventory doesn't have multiple copies of any object, this is the set packing problem. It is NP-hard, so you shouldn't expect any efficient solution. Since your problem is a generalization of a NP-hard problem, it too is NP-hard, so not solvable efficiently.

If you have to solve it in practice, you might consider formulating it as an instance of integer linear programming or SAT and then using an off-the-shelf ILP solver or SAT solver. See, e.g., https://en.wikipedia.org/wiki/Set_packing#Integer_linear_program_formulation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.