Hi,

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: $number[0]['id']=5; $number[0]['number']=500; $number[1]['id']=7; $number[1]['number']=500; $number[2]['id']=23; $number[2]['number']=750; $number[3]['id']=3; $number[3]['number']=1500; $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; 5 7 23 5&7 5&23 7&23 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! Thanks, Michael. -~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~- 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) && !IsSet($working_array[$possibly_new])){ $working_array[$possibly_new] = $candidate; } } if(($candidate <= $max) && !IsSet($working_array[$candidate])){ $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]); } return($return_array); } // 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