计算拟合框数量的算法

我有一个客户卖酒瓶。他使用可容纳 6 瓶、12 瓶、18 瓶和 21 瓶的盒子。但他只想接受完全适合这些盒子的订单。里面不能有任何空白。

E.g.

• 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个？因为18和12可以除以6。所以我的方法是：

bottles = 6a + 21b

“a”和“b”必须是整数值并且可以包含零。 “bottles”也是一个整数值。我把它改成了：

 bottles / 6 - 3,5b = a

但这并不能帮助我制定一个好的算法......我认为我的方法是正确的，但是我怎样才能非常优雅地解决这个问题呢？代数大师在哪里？ ;-)

为了扩展 maraca 的评论，我们尝试求解非负整数方程 x = 6a + 21b。由于 6 和 21 能被 3（6 和 21 的最大公约数）整除，因此 x 必须能被 3 整除。此外，如果 x 小于 21，则 x 必须能被 6 整除。

相反，如果 x 能被 6 整除，则可以设置 a = x/6 且 b = 0。如果 x 是 3 的奇数倍，则 x - 21 能被 6 整除；如果 x 至少为 21，我们可以设置 a = (x - 21)/6 且 b = 1。3 的每个倍数要么是奇数要么是偶数（因此可被 6 整除），因此这证明了马拉卡的等价主张。