On 09/10/2007, Jay Blanchard <jblanchard@xxxxxxxxxx> 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.
it is a special case of the knapsack problem - the "subset sum" problem.
You'll need to be aware that it's of exponential complexity. So make
sure your lists of possible values don't get big. Anyway, here's my
answer:
<?php
function subsetSum ($target, $list) {
$partition = (int) (sizeof($list)/2);
$listA = powerset(array_slice($list, 0, $partition));
$listB = powerset(array_slice($list, $partition));
krsort($listA, SORT_NUMERIC);
ksort($listB, SORT_NUMERIC);
$target = round($target, 2);
foreach (array_keys($listA) as $A) {
foreach (array_keys($listB) as $B) {
$sum = round($A + $B, 2);
if ($sum < $target) continue 1;
if ($sum > $target) continue 2;
return array_merge($listA[$A], $listB[$B]);
}
}
return false;
}
function powerset($list) {
if (empty($list)) return array();
$value = array_pop($list);
$A = powerset($list);
$B = array();
foreach ($A as $set) {
$set[] = $value;
$B[(string) array_sum($set)] = $set;
}
return array_merge(array("$value" => array($value)), $A, $B);
}
?>
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
