Distribute elements into bins with conditions

user_2064196 0
Viewed 81

Given a collection of

struct Person {
    string name;
    int team;
    bool swimmer;
};

vector<Person> people;

is there a "well known" algorithm to distribute them into the least number of fixed-size bins with the following conditions:

  1. No two people in the same bin can be from the same team
  2. At least one person in each bin must be a swimmer

I'm looking for a solution with the smallest number of bins required to accommodate every Person. The bins do not have to be fully filled.

If half are swimmers and the bin size is four, the easiest solution is to put one swimmer with one non-swimmer. However, the most efficient solution is to put two swimmers and two non-swimmers in a bin (team membership permitting).

The number of different teams can be greater than the size of a bin, so there would be many solutions.

Obviously, if people.size() / bin_size > number of swimmers, there would be no solution.

algorithm
2 Answers

It appears to be a variant of the Bin Packing Problem.

It's a NP-complete problem but there are plenty of algorithms in literature to solve it, both for online and offline approaches.

In your case you know the data in advance so you may want to the First-fit-decreasing (FFD) algorithm or its modified version, which run in at most O(nlog(n)).

You have to modify the standard algorithm to introduce the constraints.

user_42497140

It's pretty easy to determine the least number of bins you need. Actually, you've said it yourself.

Before explaining everything, let's discuss some parameters of this problem:

  1. let, the total no. of teams be T.
  2. let, n_x be the number of person in team x.
  3. let, s_x be the number of swimmer in team x.

So, the number of bins you need at least should be:

number of bins needed = max(n_i), where 1 <= i <= T

cause, as you've said, "No two people in the same bin can be from the same team"

and if `no. of bin` is lesser than that, you've to put two person of same team
in a common bin.

Now, let's come to the second condition: At least one person in each bin must be a swimmer. To satisfy this condition, we must know the total number of swimmers present in all teams. And the total number of swimmers are:

total no. of swimmers = sum(s_i), where 1 <= i <= T

And the second condition would fall, if total no. of swimmers < number of bins needed. Cause, then, you can never satisfy the second condition.

And, your bin_size must be at least:

bin_size = ceil( sum(n_i) / number of bins needed ), where 1 <= i <= T

If bin_size is anyhow lesser than ceil( sum(n_i) / number of bins needed ), then again, you'll fail to construct solution. Cause, it'll fail you to satisfy your first condition.

I guess, you've got the answer. And the algorithm to determine the least number of bins and put the people in those bins using the two conditions is pretty straightforward.

user_88643370
Related