Essa é complicada! Como fazer soma provável?

Estou quebrando a cabeça para desenvolver um script que faz o seguinte:

Recebe um array contendo floats e um número inteiro e verifica qual a provável e menor soma de dos itens do array e seus múltiplos para chegar ao valor do inteiro.

Trocando em miúdos, é como se eu tivesse um array contendo os valores 4.0 - 3.8 - 9.4 - 1.1 - 1.2 - 7.5 - 1.5 e quisesse obter a menor soma provável para chegar ao valor 86. No caso seria 75+11. O problema é que o computador pode "pensar" em fazer a soma de 40+12+12+11+11, que daria o mesmo resultado, mas a soma é maior que a primeira.

Difícil implementar né? Minha matemática não está muito boa ueuheuhehu

Bom eu dei uma iniciada fazendo o seguinte:

<?php

$r = '24';

$n = (int)$r;

$r = strrev($r);

$leng = strlen($r);

$comvals = array(1.0,1.1,1.2,1.3,1.5,1.6,1.8,2.0,2.2,2.4,2.7,3.0,3.3,3.6,3.9,4.3,4.7,5.1,5.6,6.2,6.8,7.5,8.2,9.1);

$resarr = array();
$resarrs = array();

function mult (&$item, $key, $fc) {
$item=$item*$fc;
}

function near($value, $array)

{

 if (count($array) == 1) return $array[0];

 sort($array);

 $index = floor(count($array) / 2);

 if ($array[$index] == $value) return $value;

 if ($value < $array[$index]) {
 return near($value, array_slice($array, 0, $index));
 }

 if ($value > $array[$index])
 return near($value, array_slice($array, $index));
}

for ($x = 0; $x <=$leng-1; $x++) {
$factor = pow(10, $x);

if (($x % 2 != 0)) {

	$v = ((int)$r[$x]*$factor)+((int)$r[$x-1]*pow(10,$x-1));
	$narr = $comvals;
	array_walk($narr, "mult", $factor);
	$val = near($v,$narr);
	$resarrs[$x] = " 1 vezes o valor de ".$val;
	$n = $n-$val;
}
}

$r = (string)$n;

$r = strrev($r);

$leng = strlen($r);

for ($x = 0; $x <=$leng-1; $x++) {
$factor = pow(10, $x);
$v = (int)$r[$x]*$factor;
if ($v == 0) continue;

for ($y = count($comvals)-1; $y >=0; $y--) {

	$ret = 0;
	for ($z = 0; $z < 50; $z++) {
 $ret = $z*$factor*$comvals[$y];
 if ($ret == $v) {
 $resarr[$x] = " ".$z." vezes o valor ".($comvals[$y]*$factor)." ";
 break;
 }
 elseif ($ret > $v) break;
	}
	if (!empty($resarr[$x])) break;
}

}

print_r($resarrs);
print_r($resarr);

?>

Está meio desorganizado. Bom, ele funciona com valores R de 9324 por exemplo, ou o valor 36, ou 50 e por aí vai. Mas quando eu coloco um 180, ele já não funciona perfeitamente. É justamente pela lógica do meu algorítimo.

Se for mais fácil ao invés de mostrar só a menor possibilidade, poderia mostrar todas elas.

Alguém me dá uma luz aí? Obrigado pessoal!

$list = array( 4.0, 3.8, 9.4, 1.1, 1.2, 7.5, 1.5 );

$list = array_map( 'strval', $list );

 function( $c ) use( $target ) {

 return $c < $target;
 }
);

$diff = ( $target - array_pop( $list ) );

$closest = getClosest( $diff, $list );

 'Target Number: %f<br /><br />
 Difference between Target Number and biggest number in list: %f<br /><br />
 Closest Number Found: %f<br /><br />
 Error Margin: %f',

 $target, $diff, $closest, $margin
);

function getClosest( $search, array $arr ) {

 $closest = null;

 foreach( $arr as $item ) {

 if( $closest == null || abs( $search - $closest ) > abs( $item - $search ) ) {

 $closest = $item;
 }
 }

 return (float) $closest;
}