Binpacking SQS batches

The other day an ex-colleague messaged me with a question about efficiently packing SQS messages into batches. He knows I am easily nerd-sniped by these kinds of problem and passed it onto me. The system in question is a background job processing library for Ruby that uses AWS SQS as the job queue. Using SQS has several scaling benefits, since it can process a near infinite number of messages per second and has tremendous storage capacity. There have been occasions where a queue contained millions of unprocessed messages without any problems. However, scaling horizontally is usually not free and SQS is not without its limitations. One such limitation is that you can submit no more than 10 messages at a time and the maximum allowed size both per message and per 10-batch of messages is 256 KB.