On Tue, 2007-10-09 at 14:01 -0500, Jay Blanchard wrote: > Good afternoon gurus and guru-ettes! > > I am searching for an algorithm that will take a list of monetary values > and determine which of these values totals a value supplied to the > widget. > > 1. I supply a value to the application and give a date range > 2. The application will query for all of the values in the date range > 3. The application will determine which of the values will total the > supplied value > a. if the total values in the date range do not add up to the > supplied value the application will return that info. (I have this done > already) > 4. The application will return the records comprising the total value > given > > For instance I supply 10.22 and a date range of 2007-10-01 to 2007-10-05 > > Values in the range; > 3.98 > 9.77 > 3.76 > 4.13 > 7.86 > 1.45 > 12.87 > 10.01 > 0.88 > > Values comprising the total; > 3.76 > 4.13 > 1.45 > 0.88 > > It is possible to have duplicate values, so we will have to assume that > the first one of the dupes is correct, the records will be sorted by > date. I have been working with a recursive function, but so far the > results are not pretty and it is getting too complex. > > FYI, this is very similar to the "knapsack problem"" in dynamic > programming.
This *IS* the knapsack problem. Just because you specify date ranges to get your values and the value isn't a knapsack doesn't change the fact that it is the same problem :) I remember having fun with genetic algorithms and the knapsack problem back in University. Cheers, Rob. -- ........................................................... SwarmBuy.com - http://www.swarmbuy.com Leveraging the buying power of the masses! ........................................................... -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
