A PHP script to find the closest subset of a list of numbers that sums to a given value.

gistfile1.aw

<?php

$numbers = array(
	-750,
	-781.92,
	-2000,
	-450,
	-1000,
	-1136.16,
	-75.6,
	-34.38,
	-800,
	-20,
	-6.03,
	-14.38,
	-350,
	-1006.56,
	-1.05,
	-0.17,
	-8,
	829.44,
	220
);
$desiredSum = -1658.88;
$minDist = null;
$minDist_I = null;

// Iterate on every possible combination
$maxI = pow(2,sizeof($numbers));
for($i=0;$i<$maxI;$i++) {
	if(!(($i+1) % 1000)) echo ".";
	
	// Figure out which numbers to select in this 
	$sum = 0;
	for($j=0;$j<sizeof($numbers);$j++) {
		if($i & (1 << $j)) {
			$sum += $numbers[$j];
		}
	}
	$diff = abs($sum - $desiredSum);

	if($minDist_I === null || $diff < $minDist) {
		$minDist_I = $i;
		$minDist = $diff;
	}
	
	if($diff == 0) break;
}

$chosen = array();
for($j=0;$j<sizeof($numbers);$j++) {
	if($minDist_I & (1 << $j)) $chosen[] = $numbers[$j];
}

echo "\nThese numbers sum to " . array_sum($chosen)  . " (closest to $desiredSum): ";
echo implode(", ", $chosen);
echo "\n";