计算拟合框数的算法 [英] Algorithm for calculating number of fitting boxes

问题描述

我有一个客户卖酒瓶.他使用的盒子有6瓶、12瓶、18瓶和21瓶的空间.但他只想接受完全适合这些盒子的订单.里面不能有空位.

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.

例如

• 33 可以:1x21 和 2x6
• 48 可以:2x21 和 1x6 或 4x12
• 26 或 35 或 61 不合适

我的第一次尝试是一种直接简单的方法.我生成一个包含许多有效数字的数组，删除重复项并对其进行排序.

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);

看起来像这样:

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!

但我想为所有可能的数字制作一个完美"的解决方案，例如我想知道 123456 是否可能.你看，为了得到这个数组必须非常大:-)

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 :-)

我尝试了一个有 2 个未知数的方程.为什么只有2个?因为 18 和 12 可以被 6 整除.所以我的方法是:

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" 和 "b" 必须是整数值并且可以包含零.瓶子"也是一个整数值.我把它改成:

"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? ;-)

推荐答案

您可以通过 3 个有效案例将此作业简化为更简单的逻辑:

You can reduce this homework to some simpler logic with 3 valid cases:

1. 21 的倍数.
2. 6 的倍数.
3. 以上的组合.

例如:

function divide_order($q) {
    $result['total'] = $q;
    // find the largest multiple of 21 whose remainder is divisible by 6
    for( $i=intdiv($q,21); $i>=0; $i-- ) {
        if( ($q - $i * 21) % 6 == 0 ) {
            $result += [
                'q_21' => $i,
                'q_6' => ( $q - $i * 21 ) / 6
            ];
            break;
        }
    }
    if( count($result) == 1 ) {
        $result['err'] = true;
    }
    return $result;
}

var_dump(
    array_map('divide_order', [99, 123456])
);

输出:

array(2) {
  [0]=>
  array(3) {
    ["total"]=>
    int(99)
    ["q_21"]=>
    int(3)
    ["q_6"]=>
    int(6)
  }
  [1]=>
  array(3) {
    ["total"]=>
    int(123456)
    ["q_21"]=>
    int(5878)
    ["q_6"]=>
    int(3)
  }
}

然后您可以应用一些简单的逻辑将多个 6 的盒子减少为 12 或 18 的盒子.

Then you can apply some simple logic to reduce multiple boxes of 6 into boxes of 12 or 18.

这篇关于计算拟合框数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！