#! perl -sw
use strict;
use Data::Dumper;

sub listm{ grep{ $_[0] & (1 << $_) }0 .. 31 }

#! build test data
my %table;
my $n=0;
for my $c ('A' .. 'T') {
	$table{ +sprintf '%s%03d', $c, ++$n } = int(20+rand 100);
}
print Dumper \%table, $/;

print scalar localtime, $/;
#! Invert table
my %reqs;
while (my ($key, $value)= each %table) {
	push @{$reqs{$value}}, $key;
}

#print Dumper \%reqs, $/;

#! get array of unique requirements
my @reqs = keys %reqs;
print 'checking permutations of ', scalar @reqs, " unique values\n@reqs\n\n";

#! test the permutations and capture those with a $total <= 400
my ($perms, @ok) = (0);
for my $perm (1 .. (2 ** @reqs)-1 ) {
	$perms++;
	my $total = 0;
	$total += $_ for @reqs[ listm($perm) ];
	next if $total > 400;
	push @ok, [$total, @reqs[ listm($perm) ] ];
#	print $total, ' : ', do{local $"='|'; "@{[ @reqs[ listm($perm)] ]}";}; #!"
}
print 'Checked ', $perms, ' possible permutations', $/;
#! sort the possible solutions
@ok = sort{ $b->[0] <=> $a->[0] } @ok;

#! check for one (or more) complete solutions
my $count=0;
1 while $ok[$count++][0] == 400;
print 'There are at least ', --$count, ' complete solutions', $/;

#! Generate solutions.
my @solutions;
for my $sol (0 .. $count-1) {
	my @n = [];
	for my $val ( @{ $ok[$sol] }[ 1..$#{$ok[$sol]} ] ) {
		my $schools = @{$reqs{$val}};
		if ($schools > 1) {
			my @m = @n;
			@n = map{
				my $school = $_;
				map{ [ @{$_}, $school ] } @m
			} @{$reqs{$val}};
		}
		else {
			push @{$_}, @{ $reqs{$val} }[0] for @n;
		}
	}
	push @solutions, @n;
}
print 'There are actually ', scalar @solutions, ' possible solutions. Alpha-sorted, the first 20 are:', $/;
@solutions = sort{ "@{$a}" cmp "@{$b}" } map { [ sort @{$_} ] } @solutions;
printf "%-50s %30s = %d\n"
	, "@{$_}"
	, "@table{ @{$_} }"
	, do{ my $t=0; $t += $_ for @table{ @{$_} }; $t; }
		for @solutions[0 .. 19];

print scalar localtime, $/;


##</code><code>##

c:\test>226210-2
$VAR1 = {
          'M013' => 39,
          'J010' => 38,
          'B002' => 78,
          'Q017' => 92,
          'I009' => 109,
          'F006' => 113,
          'N014' => 103,
          'K011' => 85,
          'C003' => 86,
          'G007' => 115,
          'R018' => 33,
          'D004' => 80,
          'L012' => 92,
          'O015' => 22,
          'T020' => 110,
          'A001' => 118,
          'S019' => 115,
          'E005' => 36,
          'H008' => 56,
          'P016' => 114
        };
$VAR2 = '
';
Sun Jan 12 11:03:53 2003
checking permutations of 18 unique values
38 39 56 80 92 85 110 78 86 103 113 114 115 109 118 22 33 36

Checked 262143 possible permutations
There are at least 127 complete solutions
There are actually 194 possible solutions. Alpha-sorted, the first 20 are:
A001 B002 C003 D004 J010                                          118 78 86 80 38 = 400
A001 B002 C003 K011 R018                                          118 78 86 85 33 = 400
A001 B002 D004 K011 M013                                          118 78 80 85 39 = 400
A001 B002 E005 F006 O015 R018                                 118 78 36 113 22 33 = 400
A001 B002 G007 H008 R018                                         118 78 115 56 33 = 400
A001 B002 H008 I009 M013                                         118 78 56 109 39 = 400
A001 B002 H008 J010 T020                                         118 78 56 38 110 = 400
A001 B002 H008 R018 S019                                         118 78 56 33 115 = 400
A001 B002 M013 O015 R018 T020                                 118 78 39 22 33 110 = 400
A001 C003 D004 H008 J010 O015                                  118 86 80 56 38 22 = 400
A001 C003 H008 K011 O015 R018                                  118 86 56 85 22 33 = 400
A001 C003 J010 N014 O015 R018                                 118 86 38 103 22 33 = 400
A001 D004 E005 H008 J010 M013 R018                          118 80 36 56 38 39 33 = 400
A001 D004 E005 H008 T020                                         118 80 36 56 110 = 400
A001 D004 F006 H008 R018                                         118 80 113 56 33 = 400
A001 D004 H008 K011 M013 O015                                  118 80 56 85 39 22 = 400
A001 D004 I009 J010 O015 R018                                 118 80 109 38 22 33 = 400
A001 D004 J010 L012 M013 R018                                  118 80 38 92 39 33 = 400
A001 D004 J010 M013 N014 O015                                 118 80 38 39 103 22 = 400
A001 D004 J010 M013 Q017 R018                                  118 80 38 39 92 33 = 400
Sun Jan 12 11:04:45 2003

c:\test>