PHP Script and max() Value

Question

Sorry for my bad English and thanks for your help in advance! I have kind of a tricky problem I've encountered while coding. Here's the point:

I need a script that essentially extracts the 5 max values of 5 arrays, that are "mixed", i.e. they contain "recurrent" values. Here is an example:

array1(a, b)
array2(a, c, d, e, g)
array3(b, d, g, h)
array4(e, t, z)
array5(b, c, d, k)

The 2 essential requests are:

1) the sum of those 5 arrays (array1+array2+array3...) MUST be the highest possible...

2) ...without repeat ANY value previously used** (e.g. if in array1 the top value was "b", this cannot be re-used as max value in arrays 3 or 5).

Currently I have this...:

 $group1 = array(a, b);
 $group = array(a, b, c, d);

 $max1a = max(group1);
 $max2a = max(group2) unset($max1a);

 $sum1 = $max1a + $max2a;

 $max2b = max(group2);
 $max1b = max(group1) 
 unset($max2b);

 $sum2 = $max1b + $max2b;

 if($sum1 > $sum2) {
    echo $sum1
 } else {
    echo $sum2
 } 

... but it's kinda impossible to use this code with 5 arrays, because I should compare 5! (120...!!!) combinations in order to find the max sum value.

I know the problem is quite difficult to explain and to solve, but I really need your help and I hope you can save me!!!

Cheers

Answer 1

I'm adding this as another answer to leave the previous one intact for someone coming across this looking for that variation on this behaviour.

Given the 2 arrays:

$array1 = array(30, 29, 20);
$array2 = array(30, 20, 10);

The maximum sum using one element from each is 59 - this is dramatically different to my previous approach (and the answers' of others) which took the max element of the first array and then the highest element of the next array that is not equal to any previously used value - this would give 50 instead.

The code you want is this:

$mainArray = array();
$mainArray[] = array(30, 29, 20);
$mainArray[] = array(30, 20, 10);

$tempArray = array();
$newArray = array();

foreach($mainArray as $innerArray) {
    $newArray = array();
    if (count($tempArray) == 0) {
        foreach ($innerArray as $value) {
            $newArray[] = array('total' => $value, 'used' => array($value));
        }
    }
    else {
        foreach ($tempArray as $key => $innerTempArray) {
            $placed = FALSE;
            foreach ($innerArray as $value) {
                if (!(in_array($value, $innerTempArray['used']))) {
                    $newArray[] = array('total' => $tempArray[$key]['total'] + $value, 'used' => $tempArray[$key]['used']);
                    $newArray[count($newArray) - 1]['used'][] = $value;
                    $placed = TRUE;
                }
            }
            if (!($placed)) {
                echo "An array had no elements that had not already been used";
                die();
            }
        }
    }
    $tempArray = $newArray;
}

$total = 0;

if (count($newArray) == 0) {
    echo "No data passed";
    die();
}
else {
    $total = $newArray[0]['total'];
}

for ($i = 0; $i < count($newArray); $i++) {
    if ($newArray[$i]['total'] > $total) {
        $total = $newArray[$i]['total'];
    }
}

var_dump($total);

EDIT - Do not repeat used variables (but repeated values are ok):

Let //$a = 30, $b = 30, $c = 25, $d = 20, $e = 19 $array1 = array($a, $c, $d); $array2 = array($b, $d, $e);

We want to choose $a from $array1 and $b from $array2 as these give the largest sum - although they're values are the same that is allowed because we only care if the names of the variables saved to that place are the same.

With the arrays in the above format there is no way of achieving the desired behaviour - the arrays do not know what the name of the variable who's value was assigned to their elements, only it's value. Therefore we must change the first part of the original answer to:

$mainArray[] = array('a', 'c', 'd');
$mainArray[] = array('b', 'd', 'e');

and also have either the of the following before the first foreach loop (to declare $a, $b, $c, $d, $e)

//either
extract(array(
    'a' => 30,
    'b' => 30,
    'c' => 25,
    'd' => 20,
    'e' => 19
));

//or
$a = 30; $b = 30; $c = 25; $d = 20; $e = 19;

The above both do exactly the same thing, I just prefer the first for neatness.

Then replace the line below

$newArray[] = array('total' => $value, 'used' => array($value));

with

$newArray[] = array('total' => ${$value}, 'used' => array($value));

The change is curly brackets around the first $value because that is then evaluated to get the variable name to use (like below example):

$test = 'hello';
$var = 'test';
echo ${$var}; //prints 'hello'

A similar change replaces

$newArray[] = array('total' => $tempArray[$key]['total'] + $value, 'used' => $tempArray[$key]['used']);

with

$newArray[] = array('total' => $tempArray[$key]['total'] + ${$value}, 'used' => $tempArray[$key]['used']);

Now the code will function as wanted :)

If you are dynamically building the arrays you are comparing and can't build the array of strings instead of variables then there is no way to do it. You would need some way of extracting "$a" or "a" from $a = 30, which PHP is not meant to do (there are hacks but they are complicated and only work in certain situations (google "get variable name as string in php" to see what I mean)

Answer 2

Assuming you have grouped together all your values in one array like this,

$array = array(
    array(1,2,3),
    array(1,2,3,4),
    array(1,2,3,4,5,6),
    array(1,2,3,4,5,6),
    array(1,2,3,4,5,6,7)
); 

Loop through $array, and get the highest value which has not been used previously,

$max = array(); 

foreach($array as $value)
    $max[] = max(array_diff($value, $max));

Calculate the sum of all values with array_sum(),

echo "The maximal sum is: ".array_sum($max);

Answer 3

I'm not sure, of i really understood your problem correctly, these are my assumptions:

• You have five arrays containing numbers
• These numbers can occur multiple times across the arrays
• You want to find the highest possible sum of elements across your arrays
• The sum uses one single value of each array
• But the sum must not use the same number twice

Is that correct?

If Yes, then:

The highest possible sum across all arrays is always the sum of the largest elements. If you do not want to use the same number twice, you can just get the maximum from the first array, remove it from all the others and then sum up all the remaining maxima.

Like so:

$arrays = array();
$arrays[] = array(1, 2);
$arrays[] = array(1, 3, 4, 5, 7);
$arrays[] = array(2, 4, 7, 8);
$arrays[] = array(5, 20, 26);
$arrays[] = array(2, 3, 4, 11);

for($i=0, $n=count($arrays); $i<$n; $i++) {
    if($i===0) {
        $a1max = max($arrays[$i]);
        $sum = $a1max;
    } else {
        $duplicate_pos = array_search($a1max, $arrays[$i]);
        if($duplicate_pos !== FALSE) {
            unset($arrays[$i][$duplicate_pos]);
        }
        $sum += max($arrays[$i]);
    }
}

echo "sum: " . $sum . "\n";

Answer 4

If by the top value you mean the first alphabetically then the following would work:

$array1 = array('a', 'b');
$array2 = array('a', 'c', 'd', 'e', 'g');
$array3 = array('b', 'd', 'g', 'h');
$array4 = array('e', 't', 'z');
$array5 = array('b', 'c', 'd', 'k');

$mainArray = array($array1, $array2, $array3, $array4, $array5);

foreach ($mainArray as $key => $value) {
    sort($mainArray[$key]);
}

$resultArray = array();

foreach($maniArray as $key1 => $value1) {
    $placed = FALSE;
    foreach ($value1 as $value2) {
        if (!(in_array($value2, $resultArray))) {
            $resultArray[] = $value2;
            $placed = TRUE;
            break;
        }
    }
    if (!($placed)) {
        echo "All the values in the " . ($key + 1) . "th array are already max values in other arrays";
        die();
    }
}

var_dump($resultArray);