title: PHP find cheapest permutation
body: <p>I have multiple products that all have sizes and I need to find the cheapest configuration that meets the minimum required size.</p>
  
  <p>For example, John needs a minimum of 10 litres of storage - it can be more, but not less. </p>
  
  <p>There are 2L, 3L, 5L, 8L and 10L options (but this can change). </p>
  
  <p>As an example, it might be cheaper to get:</p>
  
  <ul>
  <li>1x10L container OR</li>
  <li>2x5L containers OR</li>
  <li>1x2L, 1x3L and 1x5L OR</li>
  <li>4x3L (this one is over 10 L, but it is still possible that it will be cheaper)</li>
  </ul>
  
  <p>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.</p>
  
  <pre><code>
  // 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
  </code></pre>