|Perl: the Markov chain saw|
Re: knapsack problem solved by regexby blokhead (Monsignor)
|on Mar 14, 2010 at 16:02 UTC||Need Help??|
Update: answered my own question, see below.
Can you explain a little more how it works? I can see how it selects items based on value, and then enforces that there is enough weight for the combined items selected. But what I'm not seeing is how it only selects the highest-weight solution.
Here is what I thought would happen with the following instance:
The regex engine would try the following:
In other words, I would have thought that ($1, $2, $3, $4, ...), each of which has two possible assignments, would get tried out in a canonical ordering like 11111, 11110, 11101, ...
But that doesn't seem to be the case. I modified the code as follows, to print the value of $1, $2, etc, upon each backtracking branch:
Then with the example above, I always get the following output, independent of whether item 'a' or 'b' comes first in the matching:
In both cases, its first backtracking change is to change the choice of 'a', no matter whether the 'a' alternative or 'b' alternative is last!
Can you help demystify me? Somehow you are getting the regex engine to go through possible matches in the v-string not in some canonical ordering of alternatives (an easy local way to backtrack), but in order of their longest combined length (a global property of the set of alternatives)? This is the only interpretation under which the regex would actually be guaranteed to output the correct answer!
Update: I think I have demystified myself. It has to do with the string being anchored at the central '0':
That is clever!
My confusion above would have been appropriate for a regex that matched like this:
but not the one used in the OP, where the choice of v's must be snug up against the '0' character: