Assuming the problem makes sense (Q>N), yet another way to think about the problem space is to enumerate the cells like this:

1 3 5 7 2 4 6 8

Then, if we index the categories by 0...Q-1 (fine because the category order must be preserved), we can consider the location of a category to be L(category index).
The nature of this location is yet to be determined.
I see that the categories always fill up from the top down.

Now, implementation details are critical...so I may be off on a wild goose chase. I'm envisioning this target (X)HTML table as a single row with a single cell for each column. Then the top-down ordering is automatic, and we're just calculating where to put the table cell delimiters. In this case, the location L corresponds simply to the column, and I can forget about rows entirely for the analysis. Then

L(0)<=L(1)<=...<=L(Q-2)<=L(Q-1)

In particular, L(0)=1 and L(Q-1)=N. In some way, we need to track the mininum category index for each column 2...N.

Merlyn pointed out the above, in his comment about binary representation.

Untested pseudo-code follows:

my $ColumnCount = 4; # or whatever we need it to be
my $CategoryCount = 6; # or whatever we need it to be
my %Weight = ();
# TODO: initialize %Weight hash with values from 0 to Q-1
my %WeightCache = (); # to be filled with weights
# TODO: initialize weight cache to handle references to
# hashes with indexes 1..Q-1
# brute-force would iterate across combinations of 1...Q-1;
# for 6 categories and 4 columns, this is 5 choose 3 i.e. 10
sub WeightSpan
{
my ($LowBound,$HighBound) = @_;
my $WeightSum = 0;
$WeightSum += $Weight{$LowBound++}
while $LowBound<$HighBound;
return $WeightSum;
}
sub IncrementCombination
{
my ($LowBound,$HighBound,@Combination) = @_;
my $Idx = 0;
while($Combination[$Idx-1]=$HighBound-$Idx)
{
return () if 1==$Idx+scalar @Combination;
$Idx--;
};
$Combination[$Idx-1]++;
$Combination[++$Idx -1]++ while $Idx;
return @Combination;
}
sub MaximumHeight
{
my ($LowBound,$HighBound,@Combination) = @_;
my @IndexSpan = ();
# TODO: auto-init @IndexSpan: 0...scalar @Combination-1
return max(map
{$WeightCache{$Combination[$_]}{$Combination[$_+1]}
||= &WeightSpan($Combination[$_],$Combination[$_+1])}
@IndexSpan);
}
sub CrunchBestCombination
{
my ($LowBound,$HighBound,$N) = @_;
my @Combination = ();
# TODO: auto-init: fill @Combination with 1...$N-1
my @BestCombination = @LowestBounds;
my $BestHeight = &MaximumHeight($LowBound, $HighBound,
@Combination);
&IncrementCombination($LowBound, $HighBound,
@Combination);
while(@Combination)
{
my $CurrentMaxHeight =
&MaximumHeight($LowBound,$HighBound,@Combination);
if ($CurrentMaxHeight<$BestHeight)
{
$BestHeight = $CurrentMaxHeight;
@BestCombination = @Combination;
}
@Combination = &IncrementCombination($LowBound,
$HighBound, @Combination);
}
return ($BestHeight,@BestCombination);
}
my @TargetCombination = &CrunchBestCombination(1,
$ColumnCount-1, $CategoryCount);
my $BestHeight = shift(@TargetCombination);
# TODO: translate @TargetCombination into </td><td>
# cell breaks

Obviously, all TODO comments should be implemented before the code has any chance of working. Also, a number of the example functions can be made more succinct.