use strict;
use warnings;
use re 'eval';
use List::Util '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 },
);

my $str = 'v' x sum( map $_->{v}, values %items ) . '0' . 'w' x $max_weight;
#print $str, "\n";

my $i;
my $left = my $right = '';
for ( keys %items ) {
  $left .= sprintf "(?<%s>(?:%s)?)\n", $_, 'v' x $items{$_}{v};
  $right .= sprintf "(?(?{ \$%d })%s|)\n", ++$i, 'w' x $items{$_}{w};
}

my $re = sprintf "%s0\n(?=\n%s)\n", $left, $right;
#print $re;

my $sum = join '+', map length, grep length, $str =~ /$re/x;
print $sum, '=', eval $sum, "\n";
print join "\n", grep { length $+{$_} } keys %+; print "\n";

__END__