1) Surely there are a bunch of more obvious optimizations, like don't place candies where they would fall because of gravity and nothing supporting them underneath, or always placing the candies in order of largest to smallest, and ignore anything symmetrical or rotationally equivalent to a previous solution... and how much would this reduce the search space?
2) What is the actual metric for fitting in a box "in the best way"? That lower layers are as full as possible before adding upper layers? That shifting of contents is minimized while upright? That shifting of contents is minimized in any orientation? To minimize small gaps and try to make non-used space as contiguous and compact as possible? Or is the box size arbitrary and the goal is to find the minimal box volume?
3) Is there separately a metric for "good enough"? Should the metric not to be to fit in a specified box, but rather find the smallest box of a set of standard box sizes that can fit the candies, with any arbitrary arrangement rather than a "best"? Is this a much easier problem, or is it just as hard or harder?
I feel like Amazon must have solved this for all practical purposes.
I suspect that it would work well and be fast if you simply place items in order from largest to smallest by volume, filling from bottom to top, quickly determine which box sizes are too small, and then just find the first arrangement that works. Curious if there are pathological cases where that wouldn't work?