In case it wasn't immediately clear, this is referring to the NP-hard problem of allocating objects (of a particular volume and size) to bins (also of a particular volume and size) in the most efficient possible way [1], as apposed to being a binary packer [2]
Would be great with a description of the solution method. Looks like some sort of recursive guillotine-cutting heuristic.
I also cannot quite tell from the screenshot whether this solves the 2D rectangular bin packing problem, which is:
Minimize number of bins
Such that all rectangular items can be positioned within one of the bins w/o overlap.
Or a form of 2D rectangular knapsack packing problem, which is:
Select the subset of items that maximizes utilization of one bin
Such all items can be positioned within the bin w/o overlap.
Sometimes variants of the latter (dep. on utilization) are also referred to as a bin-packing problem.
Both problems are NP-hard of course -- It follows from the fact that the one dimensional variants are NP-hard. Reduce from e.g. the partition problem (divide two sets of integers into two equally summed sets).
4 comments
[ 4.2 ms ] story [ 23.8 ms ] thread[1] https://en.wikipedia.org/wiki/Bin_packing_problem [2] https://en.wikipedia.org/wiki/Executable_compression
I also cannot quite tell from the screenshot whether this solves the 2D rectangular bin packing problem, which is:
Minimize number of bins Such that all rectangular items can be positioned within one of the bins w/o overlap.
Or a form of 2D rectangular knapsack packing problem, which is:
Select the subset of items that maximizes utilization of one bin Such all items can be positioned within the bin w/o overlap.
Sometimes variants of the latter (dep. on utilization) are also referred to as a bin-packing problem.
Both problems are NP-hard of course -- It follows from the fact that the one dimensional variants are NP-hard. Reduce from e.g. the partition problem (divide two sets of integers into two equally summed sets).