php - 计算拟合框数量的算法

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”也是一个整数值。我将其转换为:

 bottles / 6 - 3,5b = a

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

Answer 1

为了扩展 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 整除)，所以这证明了 maraca 的等价性声明。