This is more of a puzzle than anything. I've actually found a solution but it is so slow I thought I lost my internet connection (see below).
Let's say I have an array of numbers, like so:
$numbers_array = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
Let's also say that I have a number some numbers, stored in variables like so:
$sum = 15;
$sum2 = 24;
$sum3 = 400;
I am trying to create a function that will return true if any of the numbers in $numbers_array
can be added together (each only used once) to form the sums:
function is_summable($array_of_nums, $sum_to_check) {
//What to put here?
}
var_dump(is_summable($numbers_array, $sum));
var_dump(is_summable($numbers_array, $sum2));
var_dump(is_summable($numbers_array, $sum3));
The above should output:
bool(true)
bool(true)
bool(false)
Because 7 + 8 = 15, 7 + 8 + 9 = 24, but no combination of 1-9 can create 200.
Here's my EXTREMELY slow solution:
function is_summable($numbers, $sum) {
//Sort provided numbers and assign numerical keys.
asort($numbers);
$numbers = array_values($numbers);
//Var for additions and var for number of provided numbers.
$total = 0;
$numbers_length = count($numbers);
//Empty var to fill below.
$code = '';
//Loop and add for() loops.
for ($i = 0; $i < $numbers_length; $i++) {
$code .= 'for ($n' . $i . ' = 0; $n' . $i . ' < ' . $numbers_length . '; $n' . $i . '++) {';
if ($i != 0) {
$code .= 'if ($n' . $i . ' != $n' . ($i - 1) . ') {';
}
$code .= '$total += intval($numbers[$n' . $i . ']);';
$code .= 'if ($total == $sum) {';
$code .= 'return true;';
$code .= '}';
}
//Add ending bracket for for() loops above.
for ($l = 0; $l < $numbers_length; $l++) {
$code .= '$total -= intval($numbers[$n' . $i . ']);';
if ($l != 0) {
$code .= '}';
}
$code .= '}';
}
//Finally, eval the code.
eval($code);
//If "true" not returned above, return false.
return false;
}
$num_arr = array(1,2,3,4,5,6,7,8,9);
var_dump(is_summable($num_arr, 24));
http://pastebin.com/1nawuwXK
As always, help is appreciated!!
PHP | array_sum() Function The array_sum() function returns the sum of all the values in an array(one dimensional and associative). It takes an array parameter and returns the sum of all the values in it. The only argument to the function is the array whose sum needs to be calculated.
To get the sum of an array of numbers:Use the Array. reduce() method to iterate over the array. Set the initial value in the reduce method to 0 . On each iteration, return the sum of the accumulated value and the current number.
You can also use Python's sum() function to find the sum of all elements in an array.
Your problem is in fact a standard algorithmic problem (as Jon mentioned knapsack problem), more specifically Subset sum problem. It can be solved in polynomial time (have look on wiki page).
Pseudocode:
initialize a list S to contain one element 0.
for each i from 1 to N do
let T be a list consisting of xi + y, for all y in S
let U be the union of T and S
sort U
make S empty
let y be the smallest element of U
add y to S
for each element z of U in increasing order do
//trim the list by eliminating numbers close to one another
//and throw out elements greater than s
if y + cs/N < z ≤ s, set y = z and add z to S
if S contains a number between (1 − c)s and s, output yes, otherwise no
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With