This in no way detracts from your very nice regex abu-solution :)

I read the wikipedia link you gave to the 0-1 knapsack problem, and as usual, the algorithmic and complexity descriptions left me cold. They talk about dynamic programming and pseudo-polynomial solutions and give an algorithm which they assess as O(nW) (time & space).

But, I think the following very straighforward algorithm, which produces the same output as yours in less than a second, is O(n)?

#! perl -slw
use strict;
use List::Util qw[ sum ];

my $max_weight = 400;
my %items      = (      # value, weight: positive integers
  'map'                    => { v => 150, w => 9 },
  'compass'                => { v => 35,  w => 13 },
  'water'                  => { v => 200, w => 153 },
  'sandwich'               => { v => 160, w => 50 },
  'glucose'                => { v => 60,  w => 15 },
  'tin'                    => { v => 45,  w => 68 },
  'banana'                 => { v => 60,  w => 27 },
  'apple'                  => { v => 40,  w => 39 },
  'cheese'                 => { v => 30,  w => 23 },
  'beer'                   => { v => 10,  w => 52 },
  'suntan_cream'           => { v => 70,  w => 11 },
  'camera'                 => { v => 30,  w => 32 },
  't_shirt'                => { v => 15,  w => 24 },
  'trousers'               => { v => 10,  w => 48 },
  'umbrella'               => { v => 40,  w => 73 },
  'waterproof_trousers'    => { v => 70,  w => 42 },
  'waterproof_overclothes' => { v => 75,  w => 43 },
  'note_case'              => { v => 80,  w => 22 },
  'sunglasses'             => { v => 20,  w => 7 },
  'towel'                  => { v => 12,  w => 18 },
  'socks'                  => { v => 50,  w => 4 },
  'book'                   => { v => 10,  w => 30 },
);

for my $key ( keys %items ) {
    my $r = $items{ $key };
    $r->{ score } = $r->{ v } / $r->{ w };
}

my @orderedKeys = sort{
    $items{ $b }{ score } <=> $items{ $a }{ score }
} keys %items;

my $weight = sum map $_->{ w }, values %items;

$weight -= $items{ pop @orderedKeys }{ w } while $weight > $max_weight
+;

my $value = 0;
$value += $items{ $_ }{ v } for @orderedKeys;

printf "%22s : %4d %4d\n", $_, @{ $items{ $_ } }{ 'v', 'w' } for @orde
+redKeys;
printf "%22s : %4d %4d\n", ' ', $value, $weight;

__END__
C:\test>knapsack.pl
                   map :  150    9
                 socks :   50    4
          suntan_cream :   70   11
               glucose :   60   15
             note_case :   80   22
              sandwich :  160   50
            sunglasses :   20    7
               compass :   35   13
                banana :   60   27
waterproof_overclothes :   75   43
   waterproof_trousers :   70   42
                 water :  200  153
                       : 1030  396
[download]