Intense (for me) sorting algorithm

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.

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 1,2, 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/

1 Reply

Know the answer? Post it — somebody with the same question will find it here.

Alan19y ago
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 1,2, 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/