Initially, I did something similar to the above replies (since I forgot to take into account the ability to have negative numbers in the p
set):
<?php
$p = [17, 4, 3];
$t = 15;
$s = [];
sort($p);
for($i = count($p) - 1; $i > -1; --$i) {
if($p[$i] === 0) continue; // prevents infinite looping from 0 values
while($t - $p[$i] >= 0) {
$t -= $p[$i];
array_push($s, $p[$i]);
}
}
if($t !== 0) die('No solution found.');
die('Solution: {'.implode(',', $s).'}');
But in order to cater for negative numbers in the p
set, you have two options (from what I can see).
The first (and less efficient method) is to just try every combination and choose the shortest combination of them. This, of course, forces you to have to loop through n^2 times, and for large values on n, this isn’t practical.
The second approach is to get as close to the solution as possible in the least possible steps (by adding together the largest possible integers), and then begin trying all test cases (of adding positive to negative numbers) to reach your target. In order to do this solution, you’ll need to have one array of positive numbers only and another array of negative numbers only. This will mean that at worst you will have to loop through n^2 times (meaning no combination was found or that it was the last combination tried), or at best you’ll only need to loop through 1 time (meaning that the first positive n tested equalled your t
value).
Here’s the above code snippet adapted to solution #2:
<?php
$log = 0;
$p = [17, -1, 3, -2];
$t = 19;
$s = [];
sort($p);
// sort the values in positive ($p1) and negative ($p2) sets
$p1 = $p2 = [];
foreach($p as $v) {
if($v === 0) continue; // remove 0 if it's in there...
if($v > 0)
array_push($p1, $v);
else
array_push($p2, $v);
}
for($i = count($p1) - 1; $i > -1; --$i) {
while($t - $p1[$i] >= 0) {
++$log;
$t -= $p1[$i];
array_push($s, $p1[$i]);
}
if($t === 0) break; // if we have our answer, don't continue
if(empty($p2)) continue; // no need to loop through negative values if there is none
// if the largest value is too big to take away, try it with a combination of negatives
for($j = count($p2) - 1; $j > -1; --$j) {
++$log;
if($t - ($p1[$i] + $p2[$j]) >= 0) {
$t -= $p1[$i] + $p2[$j];
array_push($s, $p1[$i], $p2[$j]);
break;
}
if($t === 0) break; // if we have our answer, don't continue
}
}
if($t !== 0) die('No solution found.');
die('Solution: {'.implode(',', $s).'}<br />Found in: '.$log.' move(s)');
At least that’s the conclusion I came to I’d love to hear if anyone else has a more efficient solution!
EDIT: It wasn’t necessary, but I added in logging to count the number of iterations required to find the shortest combination.