# Algorithms for two and three dimensional Knapsack

I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work?

By 2D (3D) Knapsack I mean I have a square (cube) and a I have list of objects, all data are in centimeters and are at most 20m.

• What forms do your objects have? How big is the surrounding area; has it bounded size? – Raphael Apr 24 '12 at 5:52
• Are you searching for an exact solver or are heuristics sufficient? – stefan Apr 24 '12 at 19:01
• Could you be more specific? What are "sizes", and what is $m$? What precisely is your input, what precisely are your constraints, and what precisely are you trying to optimize? – JeffE Apr 25 '12 at 11:46
• Also, what have you already tried? – JeffE Apr 25 '12 at 11:47
• The problem you're talking about isn't generally referred to as a knapsack problem; it usually goes by the name bin-packing problem, and you should be able to find a lot more information about it under that name. – Steven Stadnicki May 14 '12 at 20:36

Knapsack can be solved by dynamic programming in pseudo-polynomial time $O(nW)$ with $n$ the number of objects and $W$ the size of the knapsack. So, as long as your container is small (numerically), you can solve the problem efficiently. Note that you can adjust $W$ by changing resolution; no need to measure a shipping container to the µm, but meters are probably to coarse (depending on your objects).