这更像是一个难题.我实际上找到了一个解决方案,但它太慢了我以为我丢失了我的网络连接(见下文).
这是问题所在：
假设我有一系列数字,如下所示：
$numbers_array = array(1,2,3,4,5,6,7,8,9);
我们也说我有一些数字,存储在变量中,如下所示：
$sum = 15; $sum2 = 24; $sum3 = 400;
我正在尝试创建一个函数,如果$numbers_array中的任何数字可以加在一起(每个只使用一次)以形成总和,则返回true：
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));
以上应输出：
bool(true) bool(true) bool(false)
因为7 8 = 15,7 8 9 = 24,但1-9的组合不能产生200.
这是我极其缓慢的解决方案：
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,9);
var_dump(is_summable($num_arr,24));
一如既往,感谢帮助!!
你的问题实际上是一个标准的算法问题(正如Jon提到的背包问题),更具体地说是
Subset sum problem.它可以在多项式时间内解决(看看
wiki page).
伪代码：
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
