10

给你一组积木，用 3”×1” 和 4.5”×1” 积木搭建一个面板。

为了结构完整性，块之间的空间不得在相邻行中排列。

7.5”×1”面板有2种方式，7.5”×2”面板有2种方式，12”×3”面板有4种方式，27”×5”有7958种方式“ 控制板。构建 48”×10” 面板有多少种不同的方法？

这是我目前所理解的：

块3 x 1和4.5 x 1

我使用组合公式来找到两个块可以排列在这种大小的面板中的所有可能组合

C = 选择 --> C(n, k) = n!/r!(nr)! 一次在 r 处组合 n 组

面板：7.5 x 1 = 2 种方式-->

1（3 x 1 块）和 1（4.5 x 1 块）--> 仅使用 2 个块--> 2 C 1 = 2 路

面板：7.5 x 2 = 2 路

我在这里也使用了组合

1（3 x 1 块）和 1（4.5 x 1 块）-> 2 C 1 = 2 路

面板：12 x 3 面板 = 2 种方式-->

2（4.5 x 1 块）和 1（3 x 1 块）-> 3 C 1 = 3 路

0（4.5 x 1 块）和 4（3 x 1 块）-> 4 C 0 = 1 路

3 种方式 + 1 种方式 = 4 种方式

（这是我感到困惑的地方）

面板 27 x 5 面板 = 7958 种方式

6（4.5 x 1 块）和 0（3 x 1）--> 6 C 0 = 1 路

4（4.5 x 1 块）和 3（3 x 1 块）-> 7 C 3 = 35 路

2（4.5 x 1 块）和 6（3 x 1 块）-> 8 C 2 = 28 路

0（4.5 x 1 块）和 9（3 x 1 块）-> 9 C 0 = 1 路

1 路 + 35 路 + 28 路 + 1 路 = 65 路

正如您在此处看到的，方法的数量远不及 7958。我在这里做错了什么？

另外，我如何找到构建 48 x 10 面板的方法？因为手工操作有点困难，尤其是在尝试找到 7958 方法时。

如何编写程序来计算 7958 面板的方法数的答案？构建一个程序来计算结果会更容易吗？任何帮助将不胜感激。

4

5 回答 5

4

鉴于您的“块之间的空间不得在相邻行中排列”要求，我认为“选择”功能不直接适用。我也认为这是您的分析开始崩溃的地方：

面板：12 x 3 面板 = 2 种方式 -->

2（4.5 x 1 块）和 1（3 x 1 块）-> 3 C 1 = 3 路

0（4.5 x 1 块）和 4（3 x 1 块）-> 4 C 0 = 1 路

3 种方式 + 1 种方式 = 4 种方式

...让我们构建一些面板（1 |= 1 行，2 -= 1 列）：

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |      
|          |         |      |      
+---------------------------+

+---------------------------+
|      |          |         |            
|      |          |         |      
|      |          |         |      
+---------------------------+

+---------------------------+
|          |      |         |                  
|          |      |         |      
|          |      |         |      
+---------------------------+

在这里，我们看到有 4 种不同的基本行类型，但这些都不是有效的面板（它们都违反了“块不得排列”规则）。但是我们可以使用这些行类型来创建几个面板：

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|          |         |      |      
+---------------------------+

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|      |          |         |      
+---------------------------+

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|          |      |         |     
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|      |          |         |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|          |      |         |
+---------------------------+

...

但同样，这些都不是有效的。有效的 12x3 面板是：

+---------------------------+
|      |      |      |      | 
|          |      |         |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |      |         |
|      |      |      |      |
|          |      |         |
+---------------------------+

+---------------------------+
|          |         |      |
|      |          |         |
|          |         |      |
+---------------------------+

+---------------------------+
|      |          |         |
|          |         |      |
|      |          |         |
+---------------------------+

所以实际上有 4 个，但在这种情况下，它与您使用“选择”功能得到的结果相匹配只是一个巧合。就总面板配置而言，有4个以上。

于 2011-07-11T04:15:56.913 回答
3

  1. 找到所有方法来形成给定宽度的单行。我称之为“行类型”。 示例 12x3：有 4 种宽度为 12 的行类型：(3 3 3 3)、(4.5 4.5 3)、(4.5 3 4.5)、(3 4.5 4.5)。 我会将这些表示为差距列表。 示例：(3 6 9), (4.5 9), (4.5 7.5), (3 7.5).

  2. 对于这些行类型中的每一个，找出哪些其他行类型可以放在它上面。

    例子：

    一种。(3 6 9)适合(4.5 7.5)。_

    湾。(4.5 9)适合(3 7.5)。_

    c：(4.5 7.5)适合(3 6 9)。

    d：(3 7.5)适合(4.5 9)。

  3. 列举从这些规则构建给定高度的堆栈的方法。动态编程适用于此，因为在每个级别，您只需要最后一行类型和到达那里的方式数。

编辑：我刚在喝咖啡的时候试过这个，它有效。顺便说一句，48x10 的解决方案有 15 个十进制数字。

编辑：这里是动态编程部分的更多细节：

第 2 步中的规则转换为一系列可能的邻居。数组的每个元素对应一个行类型，并保存该行类型的可能相邻行类型的索引。

0: (2)
1: (3)
2: (0)
3: (1)

在 12×3 的情况下，每个行类型只有一个可能的相邻行类型，但通常可以更多。

动态规划从单行开始，其中每种行类型都有一种出现方式：

1 1 1 1

然后，通过为每个行类型添加可能的邻居可能在前一行上形成的方式的数量来形成下一行。在宽度为12的情况下，结果1 1 1 1又是。最后，只总结最后一行。

复杂：

  • 查找行类型对应于枚举树的叶子；这棵树中有大约(/ width 3)级别，所以这需要O(2 w/3 ) = O(2 w )的时间。

  • 检查两种行类型是否适合所需的时间与它们的长度成正比，O(w/3)。建立交叉表与行类型数的平方成正比。这使得步骤 2 O(w/3·2 2w/3 ) = O(2 w )。

  • 动态规划采用高度乘以行类型数乘以平均邻居数（我估计与行类型数成对数），O(h·2 w/3 ·w/3) = O(2 w ) .

如您所见，这完全取决于行类型的数量，这些数量随宽度呈指数增长。幸运的是，常数因子相当低，因此可以在几秒钟内解决 48×10。

于 2011-07-11T07:02:10.057 回答
1

这看起来像是您可以递归解决的问题类型。以下是您可以使用的算法的简要概述，其中包含接受前一层和剩余层数作为参数的递归方法：

  • 从初始层数开始（例如 27x5 从剩余层数 = 5 开始）和一个空的前一层
  • 测试当前层的所有可能布局
    • 尝试在我们正在构建的图层的下一个可用插槽中添加 3x1。检查 (a) 它没有超过目标宽度（例如，在 27x5 中没有超过 27 宽度）并且 (b) 它没有违反给定前一层的间距条件
    • 继续尝试将 3x1s 添加到当前层，直到我们构建了一个正好（例如）27 个单位宽的有效层
    • 如果我们不能在当前插槽中使用 3x1，请将其移除并替换为 4.5x1
    • 一旦我们有了一个有效的层，递减剩余层并将它与我们刚刚构建的层一起传递回我们的递归算法
  • 一旦我们达到了剩余层 = 0，我们已经构建了一个有效的面板，所以增加我们的计数器

这个想法是我们构建有效层的所有可能组合。一旦我们（在 27x5 示例中）有 5 个有效层相互叠加，我们就构建了一个完整的有效面板。所以算法应该只找到（并因此计算）每个可能的有效面板一次。

于 2011-07-11T03:47:35.087 回答
1

这是一个“二维装箱”问题。具有良好数学知识的人将能够提供帮助，或者您可以尝试一本关于计算算法的书。它被称为“组合 NP 难题”。我不知道这意味着什么，但“硬”部分引起了我的注意:)

我看过钢材切割程序，他们大多使用最佳猜测。在这种情况下，虽然 2 x 4.5" 垂直堆叠可以容纳 3 x 3" 英寸水平堆叠。你可能没有浪费就逃脱了。当您必须找出最佳解决方案时变得相当棘手——浪费最少的解决方案。

于 2011-07-11T04:31:20.863 回答
0

这是Java中的一个解决方案，一些数组长度检查等有点混乱，但我相信你可以很容易地改进它。

无论如何，我希望这有助于演示算法的工作原理:-)

import java.util.Arrays;

public class Puzzle
{
    // Initial solve call
    public static int solve(int width, int height)
    {
        // Double the widths so we can use integers (6x1 and 9x1)
        int[] prev = {-1};      // Make sure we don't get any collisions on the first layer
        return solve(prev, new int[0], width * 2, height);
    }

    // Build the current layer recursively given the previous layer and the current layer
    private static int solve(int[] prev, int[] current, int width, int remaining)
    {
        // Check whether we have a valid frame
        if(remaining == 0)
            return 1;

        if(current.length > 0)
        {
            // Check for overflows
            if(current[current.length - 1] > width)
                return 0;

            // Check for aligned gaps
            for(int i = 0; i < prev.length; i++)
                if(prev[i] < width)
                    if(current[current.length - 1] == prev[i])
                        return 0;

            // If we have a complete valid layer
            if(current[current.length - 1] == width)
                return solve(current, new int[0], width, remaining - 1);
        }

        // Try adding a 6x1
        int total = 0;
        int[] newCurrent = Arrays.copyOf(current, current.length + 1);
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 6;
        else
            newCurrent[0] = 6;
        total += solve(prev, newCurrent, width, remaining);

        // Try adding a 9x1
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 9;
        else
            newCurrent[0] = 9;
        total += solve(prev, newCurrent, width, remaining);

        return total;
    }

    // Main method
    public static void main(String[] args)
    {
        // e.g. 27x5, outputs 7958
        System.out.println(Puzzle.solve(27, 5));
    }
}
于 2011-07-11T04:36:31.747 回答