3 ms·
Bin packing in python
- JosephRedfern 12y agoIn 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] [1] https://en.wikipedia.org/wiki/Bin_packing_problem https://en.wikipedia.org/wiki/Bin_packing_problem [2] https://en.wikipedia.org/wiki/Executable_compression https://en.wikipedia.org/wiki/Executable_compression
- greymadder 12y agoIt wasn't immediately clear-- I assumed (2) when looking at the project and wasn't sure what was going on. Thanks for the clarification.
- towry 12y agoThanks for the information.
- joakleaf 12y agoWould 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).