algorithm - Knapsack with multiple bags and items having only weight

Question

I am trying to solve this problem and I wanted to know if there are known existing algorithms / solutions to solve this.

Problem:

I have n bags and n items (which are either equal or different weights) to fill into these bag. Each of these bags have a certain weight limit and the n items needs to be put into these bags in such a way that I can use the maximum space in each of these bags.

The bags are of equal size. Will also like to know how to solve with bags of unequal size too.

Most of the solutions I read was trying to solve a 0/1 knapsack with a weight and value. Should I consider the weight and value as same? Am I on the right track?

This is not a homework problem.

Answer 1

This is known as the bin packing problem (which is NP-hard).

By simply sorting the decreasing order by their sizes, and then inserting each item into the first bin in the list with sufficient remaining space, we get 11/9 OPT + 6/9 bins (where OPT is the number of bins used in the optimal solution). This would easily take O(n2), or possibly O(n log n) with an efficient implementation.

In terms of optimal solutions, there isn't a dynamic programming solution that's as well-known as for the knapsack problem. This resource has one option - the basic idea is:

D[{set}] = the minimum number of bags using each of the items in {set}

Then:

D[{set1}] = the minimum of all D[{set1} - {set2}] where set2 fits into 1 bag
                                                  and is a subset of set1

The array index above is literally a set - think of this as a map of set to value, a bitmap or a multi-dimensional array where each index is either 1 or 0 to indicate whether we include the item corresponding to that dimensional or not.

The linked resource actually considers multiple types, which can occur multiple times - I derived the above solution from that.

The running time will greatly depend on the number of items that can fit into a bag - it will be O(minimumBagsUsed.2maxItemsPerBag).

In the case of 1 bag, this is essentially the subset sum problem. For this, you can consider the weight the same as value and solve using a knapsack algorithm, but this won't really work too well for multiple bags.

Why not? Consider items 5,5,5,9,9,9 with a bag size of 16. If you just solve subset sum, you're left with 5,5,5 in one bag and 9 in one bag each (for a total of 4 bags), rather than 5,9 in each of 3 bags.

Subset sum / knapsack is already a difficult problem - if using it's not going to give you an optimal solution, you may as well use the sorting / greedy approach above.