0

So I need a method that will break down an order into the specified sizes. For example:

orderBreakdown(40, [4, 8, 12, 16]); Would return [16, 16, 8] (an array of the orders). It needs to have the most efficient breakdown (can't be 12, 12, 12, 4). It also has to be extremely flexible - it can fail (obviously some quantities can't be broken down, for example 39 in that case).

Right now I have:

function quantityBreakdown(int $count, array $units)
{
    sort($units);

    $units = array_reverse($units); //order units from large to small

    $orders = [];

    $original_count = $count;

    while ($count > 0 && !empty($units))
    {

        for($i = 0; $i < count($units); $i++)
        {

            $unit = $units[$i];

            while($count >= $unit){
                array_push($orders, $unit);
                $count = $count - $unit;
            }
        }

        if ($count > 0){
            $count = $original_count;
            $orders = [];
            array_shift($units);
        }

    }

    return $orders;

}

This works in a lot of cases: quantityBreakdown(19, [6, 8, 11, 17]); will return [11, 8] for example. But there are some cases when it will return non-optimal results. quantityBreakdown(36, [6, 8, 11, 17]) will return [6, 6, 6, 6, 6, 6], when optimally it should return [17, 11, 8]. I'm a bit at a loss of where to go from here.

Shane Lessard
  • 655
  • 1
  • 8
  • 18
  • Maybe I am just dense but can you explain why `quantityBreakdown(36, [6, 8, 11, 17])` should return `[17, 11, 8]`? I'm really not getting the goal of this. – ficuscr Jul 26 '17 at 20:17
  • Oh, I get it now. nevermind. – ficuscr Jul 26 '17 at 20:19
  • *The sweet scent of recursion tickles your nose* – Easton Bornemeier Jul 26 '17 at 20:22
  • @ficuscr the most efficient breakdown is using large orders wherever possible because of pricing reasons - this is for ordering food items (multiple menus, so it needs to be flexible enough to accommodate any array of order sizes) – Shane Lessard Jul 26 '17 at 20:22
  • Easton, did you mean [recursion](https://www.google.com/search?safe=off&q=recursion)? ;) – ficuscr Jul 26 '17 at 20:23
  • @EastonBornemeier Care to elaborate? Currently the method I have IS recursive in that the larges number (17 in this case) is removed and the formula is ran again without it - which works for many cases - but I'm in a situation where this has to always return either the optimal answer or a failure. There are combinations that will not work, like my last example, as that 17 should be included but only used once (if it's added twice the solution fails). – Shane Lessard Jul 26 '17 at 20:27
  • 1
    https://en.wikipedia.org/wiki/Change-making_problem – Peter de Rivaz Jul 26 '17 at 20:28
  • I would check out this post: https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum – Easton Bornemeier Jul 26 '17 at 20:29
  • You essentially are going to achieve something of a partial sum concept. Since your method is going to allow for duplicates, you will ignore the concept of a remaining array left over and just continually pass in the whole ordered list. As long as it is ordered descending, like you have done, it should return the first instance of when the largest numbers want a partial sum of 0. – Easton Bornemeier Jul 26 '17 at 20:31
  • Is this [bin packing problem](https://en.wikipedia.org/wiki/Bin_packing_problem) / first fit algorithm? – ficuscr Jul 26 '17 at 20:33
  • 1
    I am assuming an optimal solution would be one that uses the 'greedy' method of using as many large numbers as possible rather than the least amount of coins in general. For example: What is the expected output for (6, [4,3,1]).... [4,1,1] or [3,3] ? – Easton Bornemeier Jul 26 '17 at 20:38
  • @EastonBornemeier The problem is, different menus might have different requirements in that regard - so it'll eventually need to be configurable. Right now the only restaurants using the app will require the greedy method. – Shane Lessard Jul 26 '17 at 20:43
  • Well, as of right now then, what I linked and described should work (if it made sense that is, I'm happy to answer questions). You may need to check out the problem @PeterdeRivaz linked for furthering this concept without the greedy method implementation – Easton Bornemeier Jul 26 '17 at 20:44
  • Thanks @EastonBornemeier, I'll give it a shot and ask if I have any questions. – Shane Lessard Jul 26 '17 at 20:49

1 Answers1

0

Assuming that the array is ordered you can have two pivots, one at the start and one in the end. So if you want to get a specific value, you can just add both values of each of the pivots. In this sense, if the result is too small just move the left pivot so your result increase and you your result is too big move the right pivot so your result decrease. If you don't get the desired result just add more pivots so you can duplicate numbers.

Franco Tume Fiestas
  • 46
  • 2