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.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: knapsack problem solved by regex
by rubasov (Friar) on Mar 14, 2010 at 17:37 UTC | |
by BrowserUk (Patriarch) on Mar 14, 2010 at 18:05 UTC | |
by rubasov (Friar) on Mar 14, 2010 at 18:29 UTC | |
by BrowserUk (Patriarch) on Mar 14, 2010 at 18:34 UTC |
In Section
Meditations