NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

## All the Perl that's Practical to Extract and Report

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Full
Abbreviated
Hidden
• #### Pseudo-Polynomial Time Solutions(Score:1)

by Serpent (8235) on 2007.10.30 14:53 (#58670)
Actually, backtracking is not required.

By using dynamic programming, one can find all solutions in pseudo-polynomial time.

Let me know if you want example code for this.
• #### Re:(Score:1)

Oh, I know that this particular problem can be done with no backtracking.

I mean, do you think I am seriously proposing regexes as the best approach to this problem? :-)

• #### Re:(Score:1)

No - I was replying to your "Obviously, backtracking is needed" comment, that is all.

Using regular expressions for this is a nifty hack that I enjoyed reading about.
• #### Re:(Score:1)

Ah, oh. Yeah, the general case. Are you referring to things like Branch&Bound?

• #### Re:(Score:1)

I'm referring to general dynamic programming.

Building a table can help solve this problem in O(M+N), where M is linear with the price goal (the higher the price, the longer this algorithm takes) and N is linear with the number of items you have to choose from.

If one builds a table where the rows represent a price (0 cents, 5 cents, 10 cents, etc, up to the goal price) and the columns represent the items, then moving from the top-left to the bottom-right, one can fill in the table based only on information a