php获取数组中相加和最接近或等于给定值的算法（类似01背包）

Question

需要一个php算法，选出一串数组中的数字组合相加和要最接近给定值的算法。例如 ：上限值：38   给定数组值 15，20，10， 6
正确结果选定：20 10 6
这个要如何实现？求具体实现方式
之前是按从大到小排序，再相加，发现选出 20 15 10，但是其实最优的是20 10 6，求帮助

Answer 1

$a = array(20, 15, 10, 6);
$r = 38;
$d = array();
for($i=1; $i<count($a); $i++) {
  foreach(math::Combination($a, $i) as $v) $d[join(',', $v)] = abs($r - array_sum($v));
}
asort($d);
printf("最优组合: %s 误差:±%d\n", key($d), current($d));print_r($d);
最优组合: 20,10,6 误差:±2
Array
(
    [20,10,6] => 2
    [20,15] => 3
    [20,15,6] => 3
    [15,10,6] => 7
    [20,15,10] => 7
    [20,10] => 8
    [20,6] => 12
    [15,10] => 13
    [15,6] => 17
    [20] => 18
    [10,6] => 22
    [15] => 23
    [10] => 28
    [6] => 32
)其中 math::Combination 是你的工具箱中必备的求组合的方法（我的也发布过多次了）

Answer 2

math::Combination是啥？我要取出20，16，10这种格式的数组的key，而不是value，例如这边是0,2,3，怎么处理？

Answer 3

math::Combination这个是扩展类？哪有啊？

Answer 4

math::Combination这个类能否提供下呢