I searched through the archives and found the following snippit of code
from Tim Converse from late 2000.  This is great, but does anyone know
how I can adapt this so I can return all values from a multidimensional
array?  I have an id number which corresponds to a record which I need
to revisit once I get all possible combinations (not just the max which
below gives us) and I do not want to lose the link between the id and
the number.  For instance:


$max is assigned the value 1350 in this example, so we know id 3 will be
eliminated off the bat.

What I need to get back are the combinations of ID's where their
corresponding number are less than or equal to value $max.  So in this
instance I might get something like;


I have spent about 40 hours in the last three days on this problem alone
and I can honestly say I am stuck.  You guys are my last hope.  Please
help a desperate man!



Tim's code:

function maximum_subset_sum ($max, $candidate_array) {
  $working_array = array();
  while ($next = each($candidate_array)) {
    $candidate = $next['value'];
    $sums_to_date = array_keys($working_array);
    while ($marked_sum = each($sums_to_date)) {
      $known_sum = $marked_sum['value'];
      $possibly_new = $known_sum + $candidate;
      if(($possibly_new <= $max) &&
        $working_array[$possibly_new] = $candidate;
    if(($candidate <= $max) &&
      $working_array[$candidate] = $candidate;
  $max_sum = max(array_keys($working_array));
  $return_array = array($working_array[$max_sum]);
  while ($max_sum != $working_array[$max_sum]) {
      $max_sum = $max_sum - $working_array[$max_sum];
array_push($return_array, $working_array[$max_sum]);

// example use
$best_sum = maximum_subset_sum(40, array(39,23,19,14,9,5,3,2,1));
print("Largest sum is " . array_pop($best_sum));
while ($value = array_pop($best_sum)) {
   print(" + $value");
}  // will print "Best sum is 23 + 14 + 3"


PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Reply via email to