Given that you are allowed a reasonable range on the total values, a looser algorithm may be appropriate.

Try shuffling the input values, then assign them to groups arbitrarily. Sort the groups by total. Then make some trades between the highest groups and the lowest groups. (If most/all of the groups are too high, add a group with 6 zeroes in it to bring the average down and create some 4/5 item groups after the trading is done)

If there are often many solutions, this should find one of them pretty quickly. Worst case behavior is horrible, but depending on the input you may never see such a case. If you do end up with a bad problem, you can always bail out to try something more rigorous if it fails to make progress.