Is there any algorithms I can look into for this bin-packing like problem?

0
votes

I'm attempting to find a method to solve a problem that I believe is similar to bin packing, but to my understanding is slightly different. In my case the goal is to fit as many bags as possible into each bin, instead of using the least bins. Maybe it's a best fit algorithm?

In my example I have a number bins that can fit a number of bags, with each bin only taking bags that contain a specific attribute. Each bag can have a number of attributes. The goal is to make use of the largest number of bags as possible. I feel like there may be a better term to use for my problem but Im not sure.

In my case, I have full knowledge of what bins and bags are available whenever I have to sort them.

an simple example

bin 1 allows attribute X with 1 slot
bin 2 allows attribute Y with 1 slot
bin 3 allows attribute Z with 1 slot

1 bag has attribute X, Y and Z
2 bags have attribute X and Y

In this example, it's clear that the Z bag should go to bin 3. My initial idea is to loop through the bins with the lowest amount of attributes to fill them first.

Im wondering if there is any established algorithm of solving a problem like mine.

3
algorithmbin-packing
I need a bit of clarity. So the bins have an associated list of allowed attributes, or a single one? And they allow bags with any of the attributes, or exactly all, or exactly one? – Elliott

3 Answers

3
votes

You want a maximum cardinality matching in the bipartite graph between bags and slots where they can be placed. Hopcroft--Karp will do the job efficiently.

-1
votes

I'm not sure it is clear that bag with X, Y, and Z attributes should go in Bin Z. What if you had 50 bags that only had attribute Z? Maybe I don't fully understand the question...

Assuming I understand correctly, you want an even distribution between the bins.

Sort by number of attributes

if (1 attribute) 
    place in matching bin
else
    place in matching bin with lowest count

While not a perfect solution, I think it will get you started... Perhaps using the same algorithm again for each bin with the bins sorted from highest count to lowest.

-1
votes

Surely. Look into:

  • Divide and Conquer: Its basis is to divide the composite problem that you have into smaller, but similar subproblems, until you reach triviality
  • Backtracking: Tries each and every possibility and when done, compare the results (perfect, but sloooooow)
  • Dynamic Pogramming