saravankg saravankg - 4 months ago 11
PHP Question

Fetch all keys from an array which value totals comes to 100

I have an array like this:

$arr = array(25, 30, 50, 15, 20, 30);


I want to fetch all keys which values total comes to
100
or if total
100
is not possible mean it will fetch less than
100
.

I need the total 100 like

> $array[2]+$array[4]+$array[5]=100


My actual need is what combinations are comes to 100

Answer

Finally I got it. There might be better solutions, but it works ...

Your problem is complex. There are 720 possible unique permutation of an array with 6 entries. More entries means more combinations. So I first got all unique permuations and then calculate the possibilies below or equal hundred for each combination.

$array = array(25, 30, 50, 15, 20, 30);
// 'permutations' function can be found at the bottom of my post
$permutations = permutations(array_keys($array));
$combinations = array();

foreach( $permutations as $keys ) {
    $current = array("sum" => 0, "keys" => array());

    foreach( $keys as $key ) {
        if( $current["sum"] + $array[$key] <= 100 ) {
            $current["sum"] += $array[$key];
            $current["keys"][] = $key;
        }
    }

    // order the keys and create a hash of them
    // to be sure each combination only exists once in the result
    sort($current["keys"]);
    $combinations[md5(join("", $current["keys"]))] = $current;
}

// remove the hashes from array when finished
$combinations = array_values($combinations);

// the final result
print_r($combinations);

For your array, there are 11 possible combinations. Result would be:

Array (
    [0] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 1
            [2] => 3
            [3] => 4
        )
    )
    [1] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 2
            [2] => 3
        )
    )
    [2] => Array (
        [sum] => 95
        [keys] => Array (
            [0] => 1
            [1] => 2
            [2] => 3
        )
    )
    [3] => Array (
        [sum] => 95
        [keys] => Array (
            [0] => 0
            [1] => 2
            [2] => 4
        )
    )
    [4] => Array (
        [sum] => 100
        [keys] => Array (
            [0] => 1
            [1] => 2
            [2] => 4
        )
    )
    [5] => Array (
        [sum] => 85
        [keys] => Array (
            [0] => 2
            [1] => 3
            [2] => 4
        )
    )
    [6] => Array (
        [sum] => 100
        [keys] => Array (
            [0] => 0
            [1] => 1
            [2] => 3
            [3] => 5
        )
    )
    [7] => Array (
        [sum] => 95
        [keys] => Array (
            [0] => 2
            [1] => 3
            [2] => 5
        )
    )
    [8] => Array (
        [sum] => 100
        [keys] => Array (
            [0] => 2
            [1] => 4
            [2] => 5
        )
    )
    [9] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 3
            [2] => 4
            [3] => 5
        )
    )
    [10] => Array (
        [sum] => 95
        [keys] => Array (
            [0] => 1
            [1] => 3
            [2] => 4
            [3] => 5
        )
    )
)

The used permutations function is based on the php cookbook but changed four your need.

function permutations($items, $perms = array(), $result = array()) {
    if( !empty($items) )
        for( $i = count($items) - 1; $i >= 0; --$i ) {
            $newItems = $items;
            $newPerms = $perms;
            list($values) = array_splice($newItems, $i, 1);
            array_unshift($newPerms, $values);

            if( count($newPerms) == 6 )
                $result[md5(join("", $newPerms))] = $newPerms;

            $result = permutations($newItems, $newPerms, $result);
        }

    return $result;
}