Half of my answers comes from this question and the subsequent answers, so if my answer works, please vote over there, too. I'll start with a tweaked version of that code here. The gist of it is that it takes each item in a given array $numbers such as [6, 12, 18] and sees if it can sum up to $target such as 42. My tweak to this function is that I'm also passing in a $final array so that I can get something back instead of just printing.
function subset_sum(array &$final, array $numbers, int $target, array $partial = []): void
{
$s = array_sum($partial);
if ($s === $target) {
if (!in_array($partial, $final, true)) {
$final[] = $partial;
}
}
if ($s >= $target) {
return;
}
for ($i = 0; $i < count($numbers); $i++) {
$n = $numbers[$i];
$remaining = array_slice($numbers, $i + 1);
subset_sum($final, $remaining, $target, array_merge($partial, [$n]));
}
}
The problem with that function, however, is that it tries every combination of the array provided, but once a number is used it won't try it again in the same sequence. So in your case, that function would never try 18 + 18 + 6 because 18 isn't in the array twice. To fix that, we'll use array_fill to repeat our numbers as much as needed. For instance, we need 6 to be in the array seven times to target 42.
function grow_initial_array(array $numbers, int $max): array
{
$numbers = array_unique($numbers);
$ret = [];
foreach ($numbers as $n) {
assert(is_int($n));
// The maximum number of times that $n can be divided into $max
$x = (int)floor($max / $n);
// Fill our array with that many items (repeat 6 seven times for 42)
$f = array_fill(1, $x, $n);
$ret = array_merge($ret, $f);
}
return $ret;
}
For your three inputs of [18, 12, 6] this produces an array of :
Array
(
[0] => 18
[1] => 18
[2] => 12
[3] => 12
[4] => 12
[5] => 6
[6] => 6
[7] => 6
[8] => 6
[9] => 6
[10] => 6
[11] => 6
)
Next up, we need to merge this simple data back in with your business logic. There's lots of ways to do this including the array_reduce etc. functions, but I'm just going to keep it simple with nested foreach loops which might not be as performant/pretty. This code creates a new array with keys being the sum of package options. The values for those sums is another array of potential options (just in case two or more combinations sum up to the same total). The third inner array is an array of your product options as initially outlined.
function remerge_to_packages_with_sums(array $final, array $packages): array
{
$package_options = [];
foreach ($final as $numbers) {
$package_option = [];
$sum = 0;
foreach ($numbers as $n) {
foreach ($packages as $p) {
if ($p['contain'] === $n) {
$package_option[] = $p;
$sum += $p['cost'];
break;
}
}
}
if (!array_key_exists($sum, $package_options)) {
$package_options[$sum] = [];
}
$package_options[$sum][] = $package_option;
}
return $package_options;
}
That code produces the following array (only the first key is shown):
Array
(
[18] => Array
(
[0] => Array
(
[0] => Array
(
[name] => 18er
[contain] => 18
[cost] => 5
)
[1] => Array
(
[name] => 18er
[contain] => 18
[cost] => 5
)
[2] => Array
(
[name] => 6er
[contain] => 6
[cost] => 8
)
)
)
// Extra items removed for display purposes
)
)
You can pretty much stop there if you want, your answer lies in the deeply nested array. But if you want to keep going, you can transform that into a smaller array where the keys are the sum, and the values are arrays of arrays matching your initial input:
function reduce_merged_array(array $merged_array): array
{
$final = [];
foreach ($merged_array as $sum => $package_collection) {
if (!array_key_exists($sum, $final)) {
$final[$sum] = [];
}
foreach ($package_collection as $pc) {
$local = [];
foreach ($pc as $item) {
if (!array_key_exists($item['name'], $local)) {
$local[$item['name']] = 0;
}
$local[$item['name']]++;
}
$final[$sum][] = $local;
}
}
return $final;
}
Which produces:
Array
(
[15] => Array
(
[0] => Array
(
[18er] => 1
[12er] => 2
)
)
[18] => Array
(
[0] => Array
(
[18er] => 2
[6er] => 1
)
)
// Only two shown for example
)
We can put those functions to work with this code, the in-code comments should hopefully explain everything:
// Initial array
$packages = [
[
'name' => '18er',
'contain' => 18,
'cost' => 5,
],
[
'name' => '12er',
'contain' => 12,
'cost' => 5,
],
[
'name' => '6er',
'contain' => 6,
'cost' => 8,
],
];
// Get just our contain values
$values = array_column($packages, 'contain');
// This is our quantity that we are targeting
$target = 42;
// Will hold the result of potential summing options
$sum_options = [];
// Duplicate our items in values so that we can get every possible combination
$value_duplicated = grow_initial_array($values, $target);
// Calculate all possible sums
subset_sum($sum_options, $value_duplicated, $target);
if (0 === count($sum_options)) {
// TODO: Nothing found that matches
exit;
}
// Convert back to packages
$packages_with_sums = remerge_to_packages_with_sums($sum_options, $packages);
// Convert to simplified array
$reduced = reduce_merged_array($packages_with_sums);
// Sort by sum, smallest first
ksort($reduced);
// Best options
$best_price = array_key_first($reduced);
$best_priced_options = reset($reduced);
// Worst options
$worst_price = array_key_last($reduced);
$worst_priced_options = end($reduced);
The $best_priced_options and $worst_priced_options variables are arrays, just FYI, because it could be possible for two or more combinations to sum up to a given price.
