That is the classic knapsack problem. It can be approached by recognising and keeping partial solutions, adding one item a time.

Given a list of records for available players, each single item whose weight is less that the total allowed is a solution. From those solutions, build a tree-like structure containing items that can be added without exceeding the allowed total.

After Compline,
Zaxo

i saw something like this here on PM before...

#!/usr/bin/perl
use strict;
use warnings;

my $points = shift @ARGV;

# @player = ( [ value, rank, name ], ... )
# likely to sort by value,rank or rank,value

my @player = map {
    chomp;
    [ (split ':', $_)[2,1,0] ]
    } <DATA>;

sub print_player { sprintf "%s(%s)[%d]$/", @{$_[0]}[2,1,0]; }

# the sort determines the order you try to get the most of,
# i'm going for more guys with big values.

@player = sort {$b->[0] <=> $a->[0]} @player;

my $pointbuff = 'x' x $points;
my $re = join '', map("((?:x{$_->[0]})*)", @player), '(x*)';
my @counts = $pointbuff =~ /$re/;

# so fooguy(a)[4] and barguy(b)[3] would give
# '((?:x{4})*)((?:x{3})*)(x*)'
# the final capture being what's left over.
#
# with points = 11
# pointbuff = xxxxxxxxxxx
# which maches xxxx twice and then xxx once with none left over.

my @match = map {[ $_, shift @counts ]} @player;

print "$points points will get you:$/";

foreach my $match (@match) {
    printf "%d %s",
      length($match->[1]) / $match->[0][0],
      print_player($match->[0]);
}

printf "with %d left over.$/", length $counts[0];


__DATA__
blastaar:v:138
mr fixit:u:104
daredevil:r:30
blob:v:51
boomerang:e:34
wolverine:e:61
skrull commando:v:18
[download]

i don't remeber if there's a way to make it cycle through all possible matches or not.

./game.pl 4096
4096 points will get you:
29 blastaar(v)[138]
0 mr fixit(u)[104]
1 wolverine(e)[61]
0 blob(v)[51]
0 boomerang(e)[34]
1 daredevil(r)[30]
0 skrull commando(v)[18]
with 3 left over.
[download]

A simple algorithm follows from this reasoning:

• You can build at most as many figures of type 1 as your budget allows;
• Once you've chosen the number n1 of figures of type 1, you can only buy a number of figures of type 2 going from 0 to the maximum allowed by your budget (minus what you spent on type 1);
• Once you've chosen the number n1 and n2 of figures of type 1 and 2, you can only buy a number of figures of type 3 going from 0 to the maximum allowed by your budget (minus what you spent on type 1 and 2);
• Same as above for type 4 to the last

As a simple sloppy example, if you have only three types:

$p1 = ... # Price of figures of type 1
$p2 = ... # Price of figures of type 2
$p3 = ... # Price of figures of type 3
$budget = ... # Total budget

for (my $i1=0; $i1 * $p1 <= $budget; $i1++) {
    for (my $i2=0; $i2 * $p2 <= $budget - $i1 * $p1; $i2++) {
        for (my $i3=0; $i3 * $p3 <= $budget - $i1 * $p1 - $i2 * $p2; $
+i3++) {
            print "You can buy $i1 type 1 + $i2 type 2 + $i3 type 3\n"
+;
        }
    }
}
[download]

Update: I have taken for granted that you could use more than one figure of each type. If that assumption is not valid, please disregard the solution or add the additional condition that all indices ($i1, $i2 ...) should not exceed 1.

This will handle up to 32 warrior types reasonably efficiently despite being brute force. It could be adapted to handle more, but by then the number of solutions is likely to make any solution unweildy.

#! perl -slw
use strict;

sub genComb{ grep @$_, map{ my $ptn=$_; [ @_[ grep{ "${_}E0" if $ptn &
+ (1<<$_) }0 .. $#_ ] ] } 0 .. 2**@_; }
sub sum{ my $sum; $sum += $_ for @_; $sum }

my %roster = map{ ("$_->[0]($_->[1])" => $_->[2]) } map{ chomp; [ spli
+t':' ] } <DATA>;

my @possibles;
unshift(@$_, sum @roster{@$_}) , push(@possibles, $_) for genComb keys
+ %roster;

printf '%3d will get you' . (' %s') x keys(%roster) . $/, @$_
    for sort {$b->[0] <=> $a->[0]} @possibles;
# To filter the list to that set costing less than $limit
# substitute the following line for the line above
#    for grep{ $_ < $limit } sort {$b->[0] <=> $a->[0]} @possibles;


__DATA__
blastaar:v:138
mr fixit:u:104
daredevil:r:30
blob:v:51
boomerang:e:34
wolverine:e:61
skrull commando:v:18
[download]

Same code somewhat more intelligable for the sake of pretty printed

Results

One important question that I'm not quite clear on is whether you can have only one of each figure or more than one (points permitting).

Here's a simplistic approach that could work:

my @data = map +{ name => $_, value => $roster{$_} }, keys %roster;
for (fit($maxpoints, 0)) {
  print join(" ", map $data[$_]->{name}, @$_), "\n";
}

sub fit {
  my($points, $start) = @_;
  return () if $points <= 0;
  map {
    my $index = $_;
    $points < $data[$_]->{value} ? () : ([ $index ],
        map [ $index, @$_ ], fit($points - $data[$_]->{value}, $index 
++ 1))
  } $start .. $#data;
}
[download]

This assumes each figure can appear only once; to allow figures to appear multiple times, replace $index + 1 in the recursive call with $index.

I don't have time to explain the code in detail right now, I'm afraid, but one thing to note is that this will include all permissible combinations, including "deficient" combinations, ie those to which you could add another figure without exceeding the points limit. Some of those can be filtered out by a slight modification to the map:

  map {
    my $index = $_;
    $points < $data[$_]->{value} ? () : do {
      my @result = fit($points - $data[$_]->{value}, $index + 1);
      @result ? map([ $index, @$_ ], @result) : [ $index ]
  } $start .. $#data;
[download]

I forgot to mention that you can only have one of each figure in your army, and that armies are built in increments of 100 points, rarely over 1000. I want to see every possible unique combination of the figures in my list for a given number of points.

thanks again,

dan shahin
hijinx comics