Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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.

In reply to Re: knapsack problem solved by regex by BrowserUk
in thread knapsack problem solved by regex by rubasov

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others cooling their heels in the Monastery: (8)
    As of 2014-12-25 00:50 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (159 votes), past polls