Looking for ideas on automatically arranging a set of objects (furniture) in a virtual room in AS3

Question

First of all, I don't want to visually arrange 3D models dragging them with the mouse, all I want is:

Given a room of certain dimensions (L,W,H) and given a set of elements like beds, chairs, etc (with L,W,H dimensions, of course) I want to automatically arrange those elements to take advantage of the space as much as I can. So I want to be able to put as much furniture as I can in a given room. At the end I need to represent the arranged items visually, inside the room.

My first thought was to use an array of items and sorting it with array.sortOn(["l","w","h"] Array.NUMERIC) and then define a gap between the objects and make the maths to put the objects one next to another, etc. but that isn't a good approach because some items may be placed on top of another ones (boxes of the same size, boxes on top of tables, etc).

I really don't have experience on 3D programming, that's why I'm asking for help. Thanks in advance.

Answer 1

This is what's known as the "Knapsack Problem" - if you can solve it, you get a Nobel Prize ;-)

Basically you're dealing with a reasonably small number of objects in your case, so you can probably get away with brute-forcing a solution. Otherwise spend some time at Wikipedia and read up on some of the various shortcuts to approximations that have been developed over the years.