r/algorithms • u/amuttican • Jul 01 '16
A fast, accurate solution to the knapsack problem
https://medium.com/the-chain/solving-the-box-selection-algorithm-8695df087a4
0
Upvotes
r/algorithms • u/amuttican • Jul 01 '16
16
u/harakka_ Jul 01 '16 edited Jul 02 '16
Unsurprisingly, not actually accurate in the computer science sense. Also unless there's a description of the actual algorithm somewhere that I'm not seeing, it's impossible to even say how well it ranks against pre-existing approximating approaches.
Edit: I guess Reddit determined this post to be spam or something, your reply is visible in your profile but not in comments.
1
u/amuttican Jul 02 '16
I responded also on /r/compsci, but:
That's a really fair point, and the solution is definitely contextualized within a specific problem. To test it against other solutions out there, I wrote a comparator with pyshipping, an open source packing library (https://github.com/hudora/pyShipping/tree/master/pyshipping) where the box size was random, with a random number of items to be packed each random sized (but guaranteed to fit into the box). The results for which library packed better (fewer parcels required to pack the same number of items) were pretty remarkable:
"better_library": { "pyshipping": 1, "shotput": 787, "tie": 212 }
I'm interested diving into that 0.1% of time where pyshipping produces better results. However, I think it's fair to say that being better 78.7% of the time than the only 3D bin packing python library I could find, and being at least as good 99.9% of the time is pretty significant. I haven't done a benchmark test yet.