包裹打包的PHP / C ++空间计算

Question

I am working on a shopping cart project which requires a 'postage calculator' based on items that the person has in their cart.

Obviously I will be storing the item's dimensions incl. weight and padding in a database and will also store the parcel (box) size and weight that the items will go in to, incl. box padding.

Figuring the weight of the parcels will be easy but I was wondering how to go about figuring how to pack the box via PHP, that is, I would like the code to 'play tetris' with the items to make sure they get the best possible fit, giving accurate postage costs.

Does anybody have any ideas on how best to achieve this or does anybody know of a PHP Class or function that can do this?

EDIT: When I said 'best possible fit' maybe I was being optimistic! Having the script try every possible combination of package distribution within the parcel would be over the top, however I could improve the speed by writing the algoritm in C++ and running the program in PHP when the user 'checks out', the return value being an array with the parcel size and weight (which are all that are needed to calculate postage costs)

Answer 1

I don't believe anyone has already found the perfect algorithm to do this. All existing algorithms (which ususally are not public) try to get a near perfect approach, but there's just too much calculation needed to calculate each and every possibility within a reasonable amount of time.

Those trucks need to leave at a certain point of time after all. :)

Besides, calculating the ideal fit also means you must know the exact measurements of each parcel, and the person that loads the truck need to use a complex 'map' to put those parcels in exactly the way you calculated.

No, in practice, the easiest approach is to calculate the total volume, use a certain factor (like 0.95, which you can finetune on the go) and use that as a guess to how many parcels will fit in your truck. And as long as its people who load your truck, this is the best approach too. Anything else will need robots to load the truck according to your specific calculated instructions.