> Date: Tue, 9 Oct 2007 14:01:30 -0500 > From: jblanchard@xxxxxxxxxx > To: php-general@xxxxxxxxxxxxx > Subject: Looking for help with a complex algorithm > > 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. > > Just another challenging day in paradise! The first thing that came to my mind was factorials. So that may be why it got complicated quickly. You still need your recursion, but by following a factorial pattern. Given: 1 2 3 Test: 1 1+2 1+2+3 1+3 2 2+3 3 Given: 1 2 3 4 Test: 1 1+2 1+2+3 1+2+3+4 1+3 1+3+4 1+4 2 2+3 2+3+4 2+4 3 3+4 4 And I'm not sure if that covers all for the case of 3 or 4 values. Something like Permutation as opposed to Combination http://www.gomath.com/algebra/probability.php _________________________________________________________________ Help yourself to FREE treats served up daily at the Messenger Café. Stop by today. http://www.cafemessenger.com/info/info_sweetstuff2.html?ocid=TXT_TAGLM_OctWLtagline -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
