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
