In general the problem should be NP-hard. While this may not be a reduction, I am thinking of trying to pack n^2 many 1 by 1 by n bins with 1 by 1 by k bricks, where k actually means many bricks of different sizes; if I am right, bin packing can be reduced to your problem.

If the bricks are of few types, it may be possible to construct quickly tiling solutions that allow one to get nice approximations. For example, 3 of the 7 blocks used to build a Soma cube each tile the 2x2x2 cube, so given any count of those 3 kinds of blocks, you can likely come within O(1) of the maximal cubical volume achievable using little more than arithmetic; if you can generate dissections of small cubes or prisms with your input bricks, you can then quickly decide which of many rectangular prisms are nicely buildable with the given tile set, and this can be used to approximate the maximal rectangular volume, or maximal cubical volume, as desired. Note that this does not contradict the above (idea for a) reduction because k in this instance is bounded from above by some small number.

Gerhard "Ask Me About System Design" Paseman, 2011.10.15