Calculate Total Number of Packages and Package Dimensions

[caplinq]

I have a program that calculates the shipping rate to customers. In order to do this, I need to give information to UPS to calculate a rate quote. Every one of our products has got a gross weight and "individual packaged dimensions" as if each product were already packed in its own box.

I am trying to come up with a solution/equation that will calculate how many boxes I will need as well as the dimensions of each of the boxes. I have been wracking my brain to come up with the cleanest, most logical solution.

It does not have to be 100% perfect (ie, there can be gaps in the boxes), but there are some restrictions:
a) The maximum box size of ANY package is 100 x 100 x 100cm
b) Should use the smallest possible box
c) The calculation (or program) must give the total number of boxes
d) The calculation must give dimensions of each of the packages (assuming they will not all be the same size)

I think that the logical solution will FIRST package all SAME TYPE products together and then fit these into the larger package, but I can be convinced otherwise.

[TABLE="width: 1174"]
<colgroup><col><col><col><col><col><col><col><col><col><col><col></colgroup><tbody>[TR]
[TD]Product SKU[/TD]
[TD]Gross
Weight[/TD]
[TD]Weight
Unit of Measure[/TD]
[TD]Width[/TD]
[TD]Height[/TD]
[TD]Length[/TD]
[TD]Dimension
Unit Of Measure[/TD]
[TD]Number of
products ordered[/TD]
[TD]Total Gross
Weight (kg)[/TD]
[TD]Number of
Packages[/TD]
[TD]Package Dimensions
(L x W x H) in cm[/TD]
[/TR]
[TR]
[TD]Product A[/TD]
[TD]0.66[/TD]
[TD]kg[/TD]
[TD]6[/TD]
[TD]6[/TD]
[TD]22[/TD]
[TD]cm[/TD]
[TD]12[/TD]
[TD]7.92[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product B[/TD]
[TD]0.05[/TD]
[TD]kg[/TD]
[TD]10[/TD]
[TD]1[/TD]
[TD]10[/TD]
[TD]cm[/TD]
[TD]14[/TD]
[TD]0.7[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product C[/TD]
[TD]0.02[/TD]
[TD]kg[/TD]
[TD]10[/TD]
[TD]1[/TD]
[TD]10[/TD]
[TD]cm[/TD]
[TD]30[/TD]
[TD]0.6[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product D[/TD]
[TD]0.08[/TD]
[TD]kg[/TD]
[TD]10[/TD]
[TD]2[/TD]
[TD]10[/TD]
[TD]cm[/TD]
[TD]12[/TD]
[TD]0.96[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product E[/TD]
[TD]0.1[/TD]
[TD]kg[/TD]
[TD]10[/TD]
[TD]3[/TD]
[TD]10[/TD]
[TD]cm[/TD]
[TD]2[/TD]
[TD]0.2[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product F[/TD]
[TD]0.01[/TD]
[TD]kg[/TD]
[TD]10[/TD]
[TD]0[/TD]
[TD]10[/TD]
[TD]cm[/TD]
[TD]4[/TD]
[TD]0.04[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product G[/TD]
[TD]0.0225[/TD]
[TD]kg[/TD]
[TD]6[/TD]
[TD]10[/TD]
[TD]6[/TD]
[TD]cm[/TD]
[TD]8[/TD]
[TD]0.18[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product H[/TD]
[TD]0.055[/TD]
[TD]kg[/TD]
[TD]6[/TD]
[TD]10[/TD]
[TD]6[/TD]
[TD]cm[/TD]
[TD]24[/TD]
[TD]1.32[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product I[/TD]
[TD]1.69[/TD]
[TD]kg[/TD]
[TD]10.5[/TD]
[TD]10.5[/TD]
[TD]25[/TD]
[TD]cm[/TD]
[TD]2[/TD]
[TD]3.38[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product J[/TD]
[TD]1.66[/TD]
[TD]kg[/TD]
[TD]13[/TD]
[TD]13[/TD]
[TD]26[/TD]
[TD]cm[/TD]
[TD]3[/TD]
[TD]4.98[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]Product K[/TD]
[TD]2.07[/TD]
[TD]kg[/TD]
[TD]15[/TD]
[TD]15[/TD]
[TD]30[/TD]
[TD]cm[/TD]
[TD]2[/TD]
[TD]4.14[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Total Gross Weight[/TD]
[TD]24.42[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Total Number of Packages[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 1[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 2[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 3[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 4[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 5[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 6[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 7[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 8[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 9[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 10[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 11[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 12[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]Dimensions Package 13[/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[/TR]
</tbody>[/TABLE]


I would post my excel sheet if I could figure out how!