# PHP find cheapest permutation

I have multiple products that all have sizes and I need to find the cheapest configuration that meets the minimum required size.

For example, John needs a minimum of 10 litres of storage - it can be more, but not less.

There are 2L, 3L, 5L, 8L and 10L options (but this can change).

As an example, it might be cheaper to get:

• 1x10L container OR
• 2x5L containers OR
• 1x2L, 1x3L and 1x5L OR
• 4x3L (this one is over 10 L, but it is still possible that it will be cheaper)

So far I've tried looping over and over up to 4 times (because typically the maximum requirement will be 40 L), but in some cases I am running out of memory, and it doesn't seem like the most efficient way of doing it.


// Size is in mL

$available_containers = [ [ 'id' => 22700, 'price' => 1190, 'size' => 2000, ], [ 'id' => 22701, 'price' => 1245, 'size' => 3000, ], [ 'id' => 22702, 'price' => 1415, 'size' => 4000, ], [ 'id' => 22715, 'price' => 12300, 'size' => 5000, ], [ 'id' => 22706, 'price' => 1740, 'size' => 5000, ], [ 'id' => 22703, 'price' => 1510, 'size' => 5000, ], [ 'id' => 22707, 'price' => 1790, 'size' => 6000, ], [ 'id' => 22704, 'price' => 1770, 'size' => 6000, ], [ 'id' => 22708, 'price' => 2215, 'size' => 7000, ], [ 'id' => 22705, 'price' => 2195, 'size' => 8200, ], [ 'id' => 22709, 'price' => 2660, 'size' => 8200, ], [ 'id' => 22710, 'price' => 2799, 'size' => 10000, ], [ 'id' => 22711, 'price' => 2910, 'size' => 12500, ], [ 'id' => 22712, 'price' => 3260, 'size' => 15000, ], [ 'id' => 22713, 'price' => 4130, 'size' => 20000, ], [ 'id' => 22714, 'price' => 3770, 'size' => 27000, ] ];$required_size = 8; // Can change.
$container_install = 5; foreach ($available_containers as $v ){ foreach ($available_containers as $v2 ){ foreach ($available_containers as $v3 ) { foreach ($available_containers as $v4 ){$all_configs = [
[
'size' => $v['size'], 'configuration' => [$v['size'] ],
'price' => $v['price'], ], [ 'size' =>$v['size'] + $v2['size'], 'configuration' => [$v['size'], $v2['size'] ], 'price' =>$v['price'] + $v2['price'] +$container_install,
],
[
'size' => $v['size'] +$v2['size'] + $v3['size'], 'configuration' => [$v['size'], $v2['size'],$v3['size'] ],
'price' => $v['price'] +$v2['price'] + $v3['price'] +$container_install + $container_install, ], [ 'size' =>$v['size'] + $v2['size'] +$v3['size'] + $v4['size'], 'configuration' => [$v['size'], $v2['size'],$v3['size'], $v4['size'] ], 'price' =>$v['price'] + $v2['price'] +$v3['price'] + $v4['price'] +$container_install + $container_install +$container_install,
],
];

foreach ( $all_configs as$c ){
if ( $c['size'] >=$required_size ){
$configuration[] = array( 'configuration' =>$c['configuration'],
'size' => $c['size'], 'price' =>$c['price'],
);
}
}
}
}
}
}

// Sort by price.
$sorted_configs = array_sort($configuration, 'price', SORT_ASC); // This function simply sorts all permutations by price
$$$$

• That's an expensive 5L container (#22715). Sure you haven't added an extra 0? – AJNeufeld Mar 7 at 6:00
• Haha thanks @AJNeufeld. Yes. Containers are actually not what I'm calculating, but I've used it to simplify the idea. – Mando Mar 7 at 6:20
• I'd call it the cheapest combination rather than permutation, because the order doesn't matter. – 200_success Mar 7 at 6:51

This problem is an instance of Integer Linear Programming. ILP is NP-hard, so an algorithm to find the optimal solution will not be much faster than brute-force. However, a common technique to find an approximate optimum is to solve it as a Linear Programming problem without the integer restrictions, then round the results up or down as necessary. Fortunately, many libraries exist to solve non-integer LP quite efficiently.

foreach ( $available_containers as$v ){
foreach ( $available_containers as$v2 ){
foreach ($available_containers as$v3 ) {
foreach ( $available_containers as$v4 ){


When you have this many loops, it's time to think about replacing the nesting with recursion.

        $all_configs = [ [ 'size' =>$v['size'],
'configuration' => [ $v['size'] ], 'price' =>$v['price'],
],


Yes, this is very inefficient.

• It considers each one-container solution $$\N^3\$$ times, where $$\N\$$ is the number of containers.
• If the one container already meets the size requirement then it's inefficient to consider larger sets which include it.
• If you've already considered [#22707, #22704, #22708, #22705] then there's no point considering [#22704, #22707, #22708, #22705]. The simple solution is to work with indices and iterate starting at the index of the previous selection.

Again, a recursive approach would be preferable: it would kill three or four birds with one stone.

        foreach ( $all_configs as$c ){
if ( $c['size'] >=$required_size ){
$configuration[] = array( 'configuration' =>$c['configuration'],
'size' => $c['size'], 'price' =>$c['price'],
);
...

// Sort by price.
$sorted_configs = array_sort($configuration, 'price', SORT_ASC); // This function simply sorts all permutations by price
`

I don't think you need both of those comments - in fact, neither says anything which isn't obvious from the code.

However, you also don't need to build an array of solutions or to sort, at least given the specification:

I need to find the cheapest configuration that meets the minimum required size

(my emphasis). Just track the best found so far.

• Thanks Peter. There are some cases where it would be cheaper to get TWO containers over one, though. Also, there are cases where a larger container might be on special, so it might be cheaper to get a 10L over an 8L, for example. I'm not sure if you've considered this? I think I have an alternate solution now anyway. – Mando Mar 12 at 23:12
• @Mando, it might be cheaper to get containers X and Y than container Z, but I'm assuming that it will never be cheaper to get containers X and Z than just Z. If some containers have negative prices, the cheapest configuration is to buy an infinite number of those containers... – Peter Taylor Mar 12 at 23:36
• Yes - That is correct. – Mando Mar 12 at 23:52