Algorithm for calculating number of fitting boxes

Question

I've a client selling wine bottles. He uses boxes with space for 6 bottles, 12 bottles, 18 bottles and 21 bottles. But he only wants to accept orders which fit exactly into these boxes. There must not be any empty space inside.

E.g.

• 33 is ok: 1x21 and 2x6
• 48 is ok: 2x21 and 1x6 or 4x12
• 26 or 35 or 61 are not ok

For my first try was an straight simple way. I produce an array containing a lot of valid numbers, remove duplicates and order them.

$numbers = [];
$end = (int) $bottles/6 + 1;
for ($i=1; $i<=$end; $i++) {      
  $numbers[] = $i * 6;
  $numbers[] = $i * 21;
  $numbers[] = $i * 21 + 6;
  $numbers[] = $i * 21 + 6 + 6;
  $numbers[] = $i * 21 + 6 + 6 + 6;
}
$numbers = array_unique($numbers);
sort($numbers);

It looks like this:

Array
(
    [0] => 6
    [1] => 12
    [2] => 18
    [3] => 21
    [4] => 24
    [5] => 27
    [6] => 30
    [7] => 33
    [8] => 36
    [9] => 39
    [10] => 42
    [11] => 48
    [12] => 54
    [13] => 60
    [14] => 63
    ....

I can check against my list. ok, fine!

But I want to make a "perfekt" solution fitting for all possible numbers, e.g. I want to know if 123456 is possible. You see, that the array must be very huge for getting this :-)

I tried an equation with 2 unknowns. Why only 2? Because 18 and 12 can be divided by 6. So my approch was:

bottles = 6a + 21b

"a" and "b" must be integer values and may contain zero. "bottles" is an integer value, too. I transformed it to:

 bottles / 6 - 3,5b = a

But this doesn't help me to make a good algorithm... I think I'm on the right way, but how can I solve this quite elegant? Where are the algebra gurus? ;-)

Answer 1

To expand on maraca's comment, we're trying to solve the equation x = 6a + 21b over nonnegative integers. Since 6 and 21 are divisible by 3 (the greatest common divisor of 6 and 21), it is necessary that x is divisible by 3. Moreover, if x is less than 21, then it is necessary that x is divisible by 6.

Conversely, if x is divisible by 6, we can set a = x/6 and b = 0. If x is an odd multiple of 3, then x - 21 is divisible by 6; if x is at least 21, we can set a = (x - 21)/6 and b = 1. Every multiple of 3 is either odd or even (and hence divisible by 6), so this proves maraca's equivalence claim.

Answer 2

I found @vivek_23's comment challenging so I figured I would give it a try.

This code will optimize the amount to the smallest number of boxes to fill the order.

It does so by first trying with 21 boxes and if the result is not %6 then it will loop backwards to if it gets a sum that is %6 and split up the rest.

// 99 is challenging since 99 can be divided on 21 to 4, but the remainder is not % 6 (15).
// However the remainder 15 + 21 = 36 which is % 6. 
// Meaning the "correct" output should be 3 x 21 + 2 x 18 = 99
$order = 99;
$b = [21 => 0, 18 => 0, 12 => 0, 6 => 0];

// number of 21 boxes possible
if($order >= 21){
    $b[21] = floor($order/21);
    $order -= $b[21]*21;
}

// if the remainder needs to be modified to be divisible on 6
while($order % 6 != 0){
    if($b[21] > 0){
        // remove one box of 21 and add the bottles back to the remainder
        $order += 21;
        $b[21]--;
    }else{
        // if we run out of 21 boxes then the order is not possible.
        echo "order not possible";
        exit;
    }
}
// split up the remainder on 18/12/6 boxes and remove empty boxes 
$b = array_filter(split_up($b, $order));

var_dump($b);

function split_up($b, $order){
    // number of 18 boxes possible
    if($order >= 18){
        $b[18] = floor($order/18);
        $order -= $b[18]*18;
    }
    // number of 12 boxes possible
    if($order >= 12){
        $b[12] = floor($order/12);
        $order -= $b[12]*12;
    }
    // number of 6 boxes possible
    if($order >= 6){
        $b[6] = floor($order/6);
        $order -= $b[6]*6;
    }
    return $b;
}

https://3v4l.org/EM9EF