Intense (for me) sorting algorithm

Question

I'm writing a label printing application for work. Basically it needs to sort item quantities into containers. Currently I'm sorting into boxes full of one item and leaving a sorted list of items that are left over (those that don't fit into containers fully). My question is what's the best approach for developing an algorithm that can sort them into boxes trying to fill as many boxes as possible while keeping the remaining items together. For example: Containers can hold 4. Type 1 2. Type 2 3. Type 3 1. Type 4 2. Type 5 3. In this instance Type 2 and Type 3 would go in a box Type 1 and Type 4 would go in a box and Type 5 would remain by themselves. Items need to stay together (no splitting into separate boxes). Also the amount that a container can hold should be variable. Any help or insight would be appreciated.

Alan · Answer

These sorts of problems are generally quite difficult to solve though at least here the numbers are small :) Basically what you need to do is to consider all possible combinations of your 5 types (taken 12 3 4 or 5 at a time) sum the quantities and work out which combinations will fill (or best fill) the first box given the maximum capacity of a box. Then for each of those 'best fill' combinations you need to consider all possible combinations of the remaining types sum their quantities and work out which combinations will best fill the second box. And then carry on like this until you identify the partition(s) of your 5 types which will fill the most boxes. For these sort of numbers it would be possible to slog out the combination generation using nested for statements (some of them would be trivial) but for a more sophisticated approach which works with much bigger numbers I'd check out this MSDN magazine article: http://msdn.microsoft.com/msdnmag/issues/04/07/TestRun/