in reply to
knapsack problem solved by regex

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
`

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.