Determining package dimensions for UPS Shipping Rate API

Question

I am coding a custom commerce CMS in PHP.
I have been integrating the UPS XML API for getting Shipping Rates and currently have it working. I am using Mark Sandborn's PHP class http://code.google.com/p/ups-php/

The API requires input of the final package's Length, Width, Height and Weight. My product database has this info for each respective product, so no problem when someone purchases just one item. Slightly different story when multiple products are added to the cart... The final Package Weight is still easy since it I can just grab the sum of all product weights.

However what are best practices for estimating the final package's Length, Width and Height to pass to UPS when multiple products are in the cart?

Amendment
It seems to me that any developer working with the UPS API in a store environment must deal with this same issue. More so than a solution to the knapsack problem I'm hoping I am misunderstanding something about how the API works and that there's actually a simple way to deal with this or even a way to hand off this to UPS to calculate.

Answer 1

You are basically trying to find the same software that business use when designing 2D shapes. They get first a flat material surface, and then, with the objects they want to obtain, optimize the arrangement so no material is wasted.

This is not an easy task; I would say it's a huge task even considering all your objects are perfect boxes.

Also I think you could actually write a whole book about this as some people has done. If you are still willing to do it automatically instead of trying manually, read this Wikipedia article.

And here there is an old but still helpful forum conversation about it for PHP. They also suggest the try-and-see that is optimal, which I think it's your best option.