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

2 Answers 2

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$
4
  • $\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, 2012 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, 2012 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, 2012 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, 2016 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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