You won't be able to do it perfectly since it would take some human logic to figure out what can and can't be packaged together and how to fit them into what size box depends on the precise shape of the package. Writing an algorithm to capture that logic would be extremely difficult.
You will probably have to generalize and over simplify the logic to get something good enough. So I think saving the volume of each item might make sense in your case with the weight. (volume = height * width * depth)
Set thresholds for what volume is considered large, medium, and small (this should directly correspond to their delivery method decision).
Maybe you assume all large items are shipped individually.
Small and Medium items are packaged together with a maximum combined volume, and then shipped based on the combined volume.
That logic might be more reasonably calculated and may allow you to estimate shipping well enough to satisfy your customer.