Backpack with several bags and items that have only weight

Question

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

Problem:

I have n bags and n items (which are equal or different weights) to fill them. Each of these bags has a certain weight limit, and n items need to be placed in these bags so that I can use the maximum space in each of these bags.

The bags are the same size. I would also like to know how to solve problems with bags of unequal size.

Most of the solutions I read tried to solve the 0/1 radar with weight and cost. Should I consider weight and value the same? Am I on the right track?

This is not a homework problem.

Answer 1

This is called the basket packing problem (this is NP-hard).

Just sorting the descending order by their size, and then inserting each element in the first bit in the list with sufficient remaining space, we get 11/9 OPT + 6/9 buffers (where OPT is the number of bins used in the optimal solution). This can easily take O(n²) or perhaps O(n log n) with an efficient implementation.

In terms of optimal solutions, there is no dynamic programming solution, which is also known as a backpack problem. This resource has one option - the main idea:

 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 collection — think of it as a value set map, bitmap, or multidimensional array, where each index is 1 or 0 to indicate whether we include an element that matches this size or not.

A linked resource is actually considering several types that can occur several times - I deduced the above solution from this.

The operating time will greatly depend on the number of elements that can fit into the bag - this will be O(minimumBagsUsed.2 maxItemsPerBag ) .

In the case of 1 bag, this is essentially the problem of the sum of the subset . To do this, you can consider the weight as the same as the value and solve using the knapsack algorithm, but this does not work very well for several packages.

Why not? Consider elements 5,5,5,9,9,9 with bag size 16 . If you simply decide the sum of the subset, you will be left with 5,5,5 in one bag and 9 in one bag each (total bag 4 ), and not 5,9 in each of the three packages.

The total amount / backpack is already a difficult problem - if you do not use it for an optimal solution, you can use the sorting / greed method above.