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

问题描述 投票:1回答:1

[在方格纸上绘制了一个m×n的矩形板。您需要通过沿着网格线的直切将其切成mn 1×1平方。您可以堆叠几块同时切割,这被视为一次切割。设计一种算法,以最少的切割次数执行此任务。任何帮助表示赞赏

algorithm puzzle
1个回答
0
投票

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

因此解决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))
© www.soinside.com 2019 - 2024. All rights reserved.