2
\$\begingroup\$

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

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.

\$\endgroup\$
1
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Mando Mar 12 at 23:12
  • \$\begingroup\$ @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... \$\endgroup\$ – Peter Taylor Mar 12 at 23:36
  • \$\begingroup\$ Yes - That is correct. \$\endgroup\$ – Mando Mar 12 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.