# 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? Apr 24, 2012 at 5:52
• Are you searching for an exact solver or are heuristics sufficient? Apr 24, 2012 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? Apr 25, 2012 at 11:46
• Also, what have you already tried? Apr 25, 2012 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. May 14, 2012 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).

Knapsack can also be approximated arbitrarily well in polynomial time (see polynomial-time approximation schemes).

However, Knapsack only considers fitting numbers into another number; it does not care about geometrics. If you need to "puzzle", you need another problem; considering Tetris, this is probably much harder than Knapsack.

GREEDY will always find a reasonable solution, but not necessarily the optimal one. Simply put the largest object which will fit each time in the knapsack. Stop when no more objects will fit.

• No, that is not true. Note that in the Knapsack problem, objects have values, too. Filling greedily by size can yield an arbitrarily bad solution. Jul 31, 2012 at 9:07
• @Raphael: Well, not arbitrarily bad, but I wouldn't consider the greedy solution a reasonable solution. The greedy approach gets worse for the higher dimensional analogues. Aug 2, 2012 at 9:08
• @A.Schulz Actually yes arbitrarily bad! The greedy heuristic for knapsack, using either size or bang-for-buck can easily be shown to not have any finite approximation guarantee to OPT. Oct 29, 2012 at 18:56
• People... please stop saying "Well, I don't know about that! But..." before doing your %#\$( homework on it! Dec 18, 2016 at 18:46