
P is for Practical
	PerlMonks

Re: knapsack problem solved by regex

by blokhead (Monsignor)

on Mar 14, 2010 at 16:02 UTC ( #828586=note: print w/replies, xml )

Need Help??

Help for this page

Select Code to Download

Select or download this

my $max_weight = 10;
my %items      = (      # value, weight: positive integers
  'a'  => { v => 1, w => 2 },
  'b'  => { v => 11,  w => 9 },
);

Select or download this

           first half           second half
           $1  $2
attempt 1: v   vvvvvvvvvvv  --> ww + wwwwwwwww = 11, not enough w's!
backtrack
attempt 2: v   <empty>      --> ww = 2, enough w's for this, so accept
+ed

Select or download this

# used to be:
# my $re = sprintf "%s0\n(?=\n%s)\n", $left, $right;
...
my $re = sprintf qq[%s0\n(?{ print "trying " . Dumper \\%%+})\n(?=\n%s
+)\n],
    $left, $right;
print $re;

Select or download this

STRING:
vvvvvvvvvvvv0wwwwwwwwww
...
          'a' => '',
          'b' => 'vvvvvvvvvvv'
        };

Select or download this

STRING:
vvvvvvvvvvvv0wwwwwwwwww
...
          'a' => '',
          'b' => 'vvvvvvvvvvv'
        };

Select or download this

^
(?<a>(?:v)?)
(?<b>(?:vvvvvvvvvvv)?)
v*
0

Select or download this
```
(?<a>(?:v)?)
(?<b>(?:vvvvvvvvvvv)?)
0
```

Node Status^?

node history
Node Type: note [id://828586]
help

Chatterbox^?

How do I use this? | Other CB clients

Other Users^?

Others browsing the Monastery: (6)

As of 2017-06-24 02:46 GMT

Sections^?

Information^?

Find Nodes^?

Leftovers^?

Voting Booth^?