使用最少的裁切次数裁切纸张

Question

方格纸上画了一个m×n的长方形板。你需要沿着网格线通过直线切割将其切割成 mn 个 1 × 1 的正方形。您可以将几块堆叠在一起以同时切割它们，这被认为是一次切割。设计一种算法，以最少的切割次数执行此任务。任何帮助表示赞赏

Answer 1

请注意，每次切割都将沿着网格线进行，并且我们始终可以将纸张移动到所需的切割位置，而不是移动刀。这意味着如果我们有一堆纸，我们总是可以移动和堆叠每张纸，这样我们就可以在每张纸上独立地切割到所需的位置。

因此，m x n 的问题可以通过极小极大方法递归求解。设 o(m, n) 为最优方法所需的切割数。然后最佳切割是给我们两张纸的那种，尺寸为 a x b 和 c x d，这样两张纸的切割次数最多它们被最小化。我们总是可以并行切割它们（正如我们在上面看到的），所以这就是为什么只有最大值而不是它们的最佳切割的总和才算数。

最后请注意，我们只能切割 m 或 n，不能同时切割。通过这些观察，我们可以写出一个递归（我使用 Python）：

import functools

@functools.lru_cache(None)  # Memoize solution.
def o(m, n):
    if m == n == 1: return 0
    cut_candidates =  [((k, n), (m-k, n)) for k in range(1, m)]
    cut_candidates += [((m, k), (m, n-k)) for k in range(1, n)]
    return 1 + min(max(o(a, b), o(c, d))
                   for (a, b), (c, d) in cut_candidates)

通过记忆，我们可以在 m, n 上进行动态规划，我在上面就是这样做的。查看此函数的结果，我们找到了正确的序列 A096198。我们还发现有一个更简单的解决方案，即 ceil(log2(m)) + ceil(log2(n)).

使用最少的裁切次数裁切纸张

Cut paper using minimum number of cuts

puzzle

algorithm