javascript - 给定一个值,如100,给定一个数组,从数组中挑选出N个元素,这N个元素相加也是100,得到一种结果就行
var arr = [99.1, 92.2, 60, 50,
49.5, 45.7, 25.1, 20,
17.4, 13, 10, 7, 2.1, 2, 1];
找到和为100的数组元素:
[60,20,10,7,2,1]
回复内容:
如数组:
var arr = [99.1, 92.2, 60, 50,
49.5, 45.7, 25.1, 20,
17.4, 13, 10, 7, 2.1, 2, 1];
找到和为100的数组元素:
[60,20,10,7,2,1]
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 )
來個 Python 版的:
def subsetsum(elements, target):
if target==0:
return True, []
elif not elements or target
思路很簡單,當我要問 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
測試:
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)
結果:
True [60, 20, 10, 7, 2, 1]
題外話,看到這個題目覺得超熟悉,如果還要考慮到解的速度等等會更有趣。
曾經做過這方面的研究,我提出一個變形的問題,大家可以思考看看:
我們今天給定一個整數(代表負數也 ok )的 多重集 (多重集就是一個集合,但是允許元素重複出現),叫做
elements
,在給定另外一個整數的 多重集 叫做targets
,試問是否存在若干個 子多重集,每個 子多重集 的元素和恰好有一個在targets
中對應的 target。
定義看不懂沒差,我舉個例子:
elements = (1,4,6,4,1)
targets = (5,10,1)
這個例子是有解的:
(1,4) -> 5
(4,6) -> 10
(1) -> 1
注意,每個在 elements
中的元素只能被使用一次!
组合问题。看一下leetcode的原题:
function t100(array){
var tempArray = array.concat([]).sort(function(a,b){
return a-b;
});
var temp = 0;
var result = [];
for(var i=0;i100){
tempArray.length = i;
}
}
for(var i=0;i
递归内套一个循环
下一篇: 精简压缩jre