O que você está propondo é essencialmente uma variação do Problema da Mochila , com a diferença adicional de que, devido ao processo compressão, você não começa a saber quanto de sua "mochila" de 20MB cada item ocupará.
A solução trivial, é claro, seria simplesmente zipar cada arquivo de forma independente, mas isso não reduz a contagem de arquivos, então eu suspeito que não seria uma solução satisfatória.
Se eu fosse apresentado a esse problema, suponho que começaria compactando cada arquivo individualmente para um local temporário (ou na memória, sem gravá-los em disco), apenas para obter um tamanho compactado aproximado para cada . Com essa informação, seria então possível decidir quais arquivos devem ser agrupados por qualquer uma das abordagens padrão para o Problema da Mochila e criar os arquivos zip reais.
Supondo que você tenha uma linguagem de script disponível para você e saiba como usá-la, eu esperaria que essa abordagem fosse bastante simples de automatizar; fazer isso manualmente seria muito tedioso se você tivesse mais do que um punhado de arquivos para lidar ...