Knapsack with multiple bags and items having only weight

by

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(n²), 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.

More Related Contents:

  1. Variation on knapsack – minimum total value exceeding ‘W’
  2. Complexity of absolute difference and sum
  3. C++ Sorting Algorithms [closed]
  4. What is tail recursion?
  5. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  6. Getting the closest string match
  7. How to compute Discrete Fourier Transform?
  8. Difference between Big-O and Little-O Notation
  9. How does finding a cycle start node in a cycle linked list work?
  10. Efficient list intersection algorithm
  11. Rounding to an arbitrary number of significant digits
  12. What would cause an algorithm to have O(log log n) complexity?
  13. search for interval overlap in list of intervals?
  14. robust algorithm for surface reconstruction from 3D point cloud?
  15. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  16. 3D Least Squares Plane
  17. Is there ever a good reason to use Insertion Sort?
  18. How to implement tag system
  19. Shortest distance between points algorithm
  20. Amortized complexity in layman’s terms?
  21. In Order Successor in Binary Search Tree
  22. Coin changing algorithm
  23. What is the advantage to using Bloom filters?
  24. algorithm for index numbers of triangular matrix coefficients
  25. Search a sorted 2D matrix [duplicate]
  26. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  27. Draw equidistant points on a spiral
  28. Comparison-based ranking algorithm
  29. Location of highest density on a sphere
  30. Why is the “start small” algorithm for branch displacement not optimal?

Leave a Comment