PHP find cheapest permutation

Question

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

n x n x n x n is not a good complexity. you may try this recursive function https://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm — Josua Marcel C, Mar 07 '19 at 01:26
What you should do is loop once, with probably a while loop, then use division to get the number of times it goes into each one (in order of largest to smallest) Subtract that value out, and do it again. Reducing the original value each time. — ArtisticPhoenix, Mar 07 '19 at 01:27
This seems to be more of a question for https://codereview.stackexchange.com/ — Jeff, Mar 07 '19 at 01:27
@ArtisticPhoenix - I'm no mathematical genius - just a programmer haha. Can you clarify with an example? — Mando, Mar 07 '19 at 01:35
`$available_containers` is not a valid array, it's some weird combination of print_r and something else. And how does this `[size] => 5000` compare to {n}L — ArtisticPhoenix, Mar 07 '19 at 01:35
@Jeff - I haven't used codereview - how is it different to Stackoverflow? — Mando, Mar 07 '19 at 01:35
Thanks @ArtisticPhoenix - it was a mix of both. I have edited it now. — Mando, Mar 07 '19 at 01:38
SO is for specific coding problems you can't solve ("This should work, because ..., but gives me this unexpected result"), whereas codereview is more for "This code works, but doesn't look right. Is there a better way?" — Jeff, Mar 07 '19 at 01:38
@Mando - What I was thinking wont work anyway, you need to find all combinations, then figure the price for each one, then choose the cheapest one, I was thinking fit the fewest number of containers. — ArtisticPhoenix, Mar 07 '19 at 01:38
Sounds a bit like the "set cover problem" (NP complete) -- although you don't need the whole universe, just something that adds to >= 10L. Not sure if that makes it different or not. Or maybe the knapsack problem (https://stackoverflow.com/q/7949705/65387). I was never good at these proofs. — mpen, Mar 07 '19 at 01:56
Hmm thanks @mpen - I haven't heard of those things before, but I will look into it. — Mando, Mar 07 '19 at 02:00

score 0 · Answer 1 · edited Mar 08 '19 at 00:30

Well, there are some points can make these loops light weight. This problem must be solved with divide and conquer approach.

Create a subarray, because you don't need whole array, a new subarray from 1L to 10L only.
The sub array should be sorted in order by price, from lowest to height.
If and only if the lowest price which represent in first index can only bought one times, break the loop.
Otherwise, you should have a list which take the output when you already looping.

PHP find cheapest permutation

1 Answers1