1
$\begingroup$

The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of the packing. When researching knapsack problems all of the different variations I came across had a weight constraint and most didn't consider geometrical 3D space as a constraint. So my question is: is my problem considered a knapsack problem and/or is there a different term for these kind of problems which I could look into further?

$\endgroup$
1
$\begingroup$

In the standard Knapsack problem (solvable by DP) when we are packing objects we do not care about how we put objects in the knapsack, i.e., what only matters is a subset of objects and the sum of weights of these objects. But, in cuboid/rectangle packing problem the configuration of the cubes/rectangle is important to achieve the optimal packing. So, from this point of view these problems are different. I googled and found this heuristic approach and this article.

$\endgroup$

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.