8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What forms do your objects have? How big is the surrounding area; has it bounded size? $\endgroup$ – Raphael Apr 24 '12 at 5:52
  • $\begingroup$ Are you searching for an exact solver or are heuristics sufficient? $\endgroup$ – stefan Apr 24 '12 at 19:01
  • 1
    $\begingroup$ 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? $\endgroup$ – JeffE Apr 25 '12 at 11:46
  • 1
    $\begingroup$ Also, what have you already tried? $\endgroup$ – JeffE Apr 25 '12 at 11:47
  • 4
    $\begingroup$ 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. $\endgroup$ – Steven Stadnicki May 14 '12 at 20:36
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Jul 31 '12 at 9:07
  • $\begingroup$ @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. $\endgroup$ – A.Schulz Aug 2 '12 at 9:08
  • $\begingroup$ @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. $\endgroup$ – Aaron Oct 29 '12 at 18:56
  • $\begingroup$ People... please stop saying "Well, I don't know about that! But..." before doing your %#$( homework on it! $\endgroup$ – MickLH Dec 18 '16 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.