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' =&gt; 22700,
  'price' =&gt; 1190,
  'size' =&gt; 2000,
],
[
  'id' =&gt; 22701,
  'price' =&gt; 1245,
  'size' =&gt; 3000,
],
[
  'id' =&gt; 22702,
  'price' =&gt; 1415,
  'size' =&gt; 4000,
],
[
  'id' =&gt; 22715,
  'price' =&gt; 12300,
  'size' =&gt; 5000,
],
[
  'id' =&gt; 22706,
  'price' =&gt; 1740,
  'size' =&gt; 5000,
],
[
  'id' =&gt; 22703,
  'price' =&gt; 1510,
  'size' =&gt; 5000,
],
[
  'id' =&gt; 22707,
  'price' =&gt; 1790,
  'size' =&gt; 6000,
],
[
  'id' =&gt; 22704,
  'price' =&gt; 1770,
  'size' =&gt; 6000,
],
[
  'id' =&gt; 22708,
  'price' =&gt; 2215,
  'size' =&gt; 7000,
],
[
  'id' =&gt; 22705,
  'price' =&gt; 2195,
  'size' =&gt; 8200,
],
[
  'id' =&gt; 22709,
  'price' =&gt; 2660,
  'size' =&gt; 8200,
],
[
  'id' =&gt; 22710,
  'price' =&gt; 2799,
  'size' =&gt; 10000,
],
[
  'id' =&gt; 22711,
  'price' =&gt; 2910,
  'size' =&gt; 12500,
],
[
  'id' =&gt; 22712,
  'price' =&gt; 3260,
  'size' =&gt; 15000,
],
[
  'id' =&gt; 22713,
  'price' =&gt; 4130,
  'size' =&gt; 20000,
],
[
  'id' =&gt; 22714,
  'price' =&gt; 3770,
  'size' =&gt; 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' =&gt; $v['size'],
            'configuration' =&gt; [ $v['size'] ],
            'price' =&gt; $v['price'],
          ],
          [
            'size' =&gt; $v['size'] + $v2['size'],
            'configuration' =&gt; [ $v['size'], $v2['size'] ],
            'price' =&gt; $v['price'] + $v2['price'] + $container_install,
          ],
          [
            'size' =&gt; $v['size'] + $v2['size'] + $v3['size'],
            'configuration' =&gt; [ $v['size'], $v2['size'], $v3['size'] ],
            'price' =&gt; $v['price'] + $v2['price'] + $v3['price'] + $container_install + $container_install,
          ],
          [
            'size' =&gt; $v['size'] + $v2['size'] + $v3['size'] + $v4['size'],
            'configuration' =&gt; [ $v['size'], $v2['size'], $v3['size'], $v4['size'] ],
            'price' =&gt; $v['price'] + $v2['price'] + $v3['price'] + $v4['price'] + $container_install + $container_install + $container_install,
          ],
        ];


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


// Sort by price.
$sorted_configs = array_sort($configuration, 'price', SORT_ASC); // This function simply sorts all permutations by price
```
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.