Optimizing the positioning of shoe boxes in a carton

I am developing an application that calculates required shipping carton dimensions for shoe boxes. The application is specifically for cartons containing a mixed selection of shoe boxes.

In addition to calculating the required dimensions, I have also been asked to determine the optimal placement of the shoe boxes within the carton. Optimization means calculating the smallest shipping carton size, while placing the four longest boxes in the corners (this adds strength to the shipping carton).

There are 12 shoe boxes in a carton, 3 rows and 4 columns. (actually there are also 9 and 18 packs but 12 will do for the example) What I have to do is find the configuration which chooses the narrowest rows, after placing the 4 longest boxes in the corners.

The width of a row is the combined width of the 3 shoe boxes in that row.

I started by omitting the four longest boxes, then resorting by narrowest and putting them in the centre column. This did not work as the longest box may also be the narrowest one - as in the below example.

I then tried to do it by trying to examine every possible combination for every row, but my brain hurt after a while of trying that .

Here is a real example. This particular carton contains only two box sizes. There are 6 of each shoe box in the shipping carton.

Shoe box “A” is 330mm long x 195mm wide x 115mm high.

Shoe box “B” is 320mm long x 235mm wide x 125mm high.

The following configuration is correct as it results in a max width of 665mm, and the longer boxes (“A”) are in the corners:

ABA

BAB (or ABB or BBA)

BAB (or ABB or BBA)

ABA

The following configuration is wrong. The longer boxes are in the corners but it results in a max width of 705mm for row 1:

AAA

BBB

BAB

ABA

Any suggestions for how do I get it to choose the correct configuration ??