javascript - 给定一个值,如100，给定一个数组，从数组中挑选出N个元素，这N个元素相加也是100，得到一种结果就行-php教程-PHP中文网

javascript - 给定一个值,如100，给定一个数组，从数组中挑选出N个元素，这N个元素相加也是100，得到一种结果就行

php中文网

发布： 2016-07-06 13:53:18

原创

1327人浏览过

如数组：

<code>var arr = [99.1, 92.2, 60, 50,
           49.5, 45.7, 25.1, 20, 
           17.4, 13, 10, 7, 2.1, 2, 1];
</code>

登录后复制

找到和为100的数组元素：

<code>[60,20,10,7,2,1]
</code>

登录后复制

回复内容：

如数组：

<code>var arr = [99.1, 92.2, 60, 50,
           49.5, 45.7, 25.1, 20, 
           17.4, 13, 10, 7, 2.1, 2, 1];
</code>

登录后复制

找到和为100的数组元素：

<code>[60,20,10,7,2,1]
</code>

登录后复制

<code>function f($n, $arr) { //$n是目标数字，$arr是数字组成的数组
    if (empty($arr)) return false; //如果数组没有元素，返回
    if (in_array($n, $arr)) return [$n];//如果期望的值已经存在，直接返回这个值
    foreach($arr as $k => $v) { //遍历数组
        if ($v > $n) continue; //比指定数还大，过
        $copy = $arr; //复制数组
        unset($copy[$k]); //去掉复制数组中已经被选中的数字
        $next = f($n - $v, $copy); //递归计算
        if(! empty($next)) return array_merge([$v], $next); //合并结果集
    }
    return false;//没找到啊
}
$arr = [99.1, 92.2, 60, 50, 49.5, 45.7, 25.1, 20, 7.4, 13, 10, 7, 2.1, 2, 1];
$data = f(100, $arr);
print_r($data);//Array ( [0] => 60 [1] => 20 [2] => 13 [3] => 7 ) 
$data = f(105, $arr);
print_r($data);//Array ( [0] => 60 [1] => 20 [2] => 13 [3] => 10 [4] => 2 ) </code>

登录后复制

來個 Python 版的:

立即学习“Java免费学习笔记（深入）”；

<code>def subsetsum(elements, target):
    if target==0:
        return True, []
    elif not elements or target < 0:
        return False, None

    result, subset = subsetsum(elements[:-1], target-elements[-1])
    return (True, subset + [elements[-1]]) if result else subsetsum(elements[:-1], target)</code>

登录后复制

思路很簡單，當我要問 elements 是否能加出 target 時，只有兩種可能:

我要使用 element[-1] 才能加出 target -> 我要能夠使用 elements[:-1] 加出 target-elements[-1] 才行
我不需要使用 element[-1] 就能加出 target -> 我要能夠使用 elements[:-1] 加出 target 才行

boundary condition 是:

當 target 為 0 時，代表我什麼都不用就能加出來，所以 return True, []
當 elements 為空或是 target 為負值時，代表永遠都加不出來了，所以 return False, None

N世界
一分钟搭建会展元宇宙

36

查看详情

測試:

<code>elements = [99.1, 92.2, 60, 50, 49.5, 45.7, 25.1, 20, 17.4, 13, 10, 7, 2.1, 2, 1]
target = 100
result, subset = subsetsum(elements, target)
print(result, subset)</code>

登录后复制

結果:

<code>True [60, 20, 10, 7, 2, 1]</code>

登录后复制

題外話，看到這個題目覺得超熟悉，如果還要考慮到解的速度等等會更有趣。

曾經做過這方面的研究，我提出一個變形的問題，大家可以思考看看:

我們今天給定一個整數(代表負數也 ok )的多重集 (多重集就是一個集合，但是允許元素重複出現)，叫做 elements，在給定另外一個整數的多重集叫做 targets，試問是否存在若干個子多重集，每個子多重集的元素和恰好有一個在 targets 中對應的 target。

定義看不懂沒差，我舉個例子:

<code>elements = (1,4,6,4,1)
targets = (5,10,1)</code>

登录后复制

這個例子是有解的:

<code>(1,4) -> 5
(4,6) -> 10
(1) -> 1</code>

登录后复制

注意，每個在 elements 中的元素只能被使用一次!

组合问题。看一下leetcode的原题:

<code>function t100(array){
  var tempArray = array.concat([]).sort(function(a,b){
    return a-b;
  });
  var temp = 0;
  var result = [];
  for(var i=0;i<tempArray.length;i++){
    if(tempArray[i]>100){
      tempArray.length = i;
    }
  }
  for(var i=0;i<tempArray.length;i++){
    temp+=tempArray[i];
    result.push(tempArray[i]); 
    if(temp==100){
      console.log("已经找到相加得100的数字们:",result)
      return result;
    }
    else{
      console.log("暂时没有计算出相加得100的数字们")      
    }
  }
}
t100([10,10,10,10,20,20,234,244,20,40]);</code>

登录后复制

递归内套一个循环