Little big bag
Have you seen the little big bag in the shop? Noticed the URL http://littlebigbag.free.fr/?
I did, and became curious. It seemed worth the try, and after a couple of times of usage it turns out to be a nice shopping bag.
It can store a lot of volume (making it look very funny) and quite some weight (if distributed evenly).
The advantages are definitely that it keeps your arms free, and that it stays small when carrying small things.
It sets you back about 8 Euro if I remember correctly.
And believe me, the sight of people watching in awe when you pack 20 liter of groceries into a flower-themed double-sided stretch condom is truly priceless