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

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.

## Pseudo-Polynomial Time Solutions (Score:1)

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)

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:Pseudo-Polynomial Time Solutions (Score:1)

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 above and to the left. When the table is filled in, the bottom-right-hand cell contains the information needed to print all solutions to the problem.

I have code, if you are interested.

Reply to ThisParent