计算试衣箱数量的算法

Question

我有一个销售葡萄酒瓶的客户。他使用带有6个瓶子，12个瓶子，18个瓶子和21个瓶子的空间的盒子。但是他只想接受完全适合这些包装盒的订单。内部不得有任何空白空间。

例如

• 33可以：1x21和2x6
• 48可以：2x21和1x6或4x12
• 26或35或61不好

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

$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
    ....

我可以核对清单。好的！

但是我想为所有可能的数字制作一个“完美”的解决方案，例如，我想知道123456是否可能。您会看到，数组必须非常大才能获得:-)

我尝试了2个未知数的方程式。为什么只有2个？因为18和12可以除以6。所以我的方法是：

bottles = 6a + 21b

“ a”和“ b”必须为整数，并且可以包含零。“瓶”也是整数。我将其转换为：

 bottles / 6 - 3,5b = a

但这并不能帮助我制定好的算法...我认为我的方法正确，但是如何解决这个问题呢？代数大师在哪里？;-)

Answer 1

function winePacking(int $bottles): bool {
    return ($bottles % 6 == 0 || ($bottles % 21) % 3 == 0);
}

https://3v4l.org/bTQHe

代码背后的逻辑：

您正在处理简单的数字，6,12,18 都可以被 mod 6 覆盖，因为 6 可以包含所有 3 个数字。21 我们可以检查 mod 21，如果它介于两者之间，那么它就是 mod 21 mod 6。

就这么简单。