Not a solution, just an unfinished thought: Maybe you can abuse Algorithm::Bucketizer or Algorithm::BinPack for your purposes - or take a look at their optimization algorithms, and adapt them for your need.
The problems are related, though not quite the same.
Perl 6 - links to (nearly) everything that is Perl 6.
Comment on Re: Creating a sub-list constrained by an average while maintaining maximum number of original elements