叠瓦片（困难算法）

Question

叠瓦片（困难算法）

3

这是一个来自编程竞赛的问题，我发现很难想出任何可行的算法来解决它。因此，我不是在寻找代码，而是要求一步一步的算法来解决它。

铺瓷砖

把瓷砖堆放在墙壁上是Bongani最喜欢的消遣之一。他所有的瓷砖厚度相同，但宽度和高度不同。Bongani获得了N块瓷砖，并按照一组规则使用它们。他只能将一块瓷砖放在另一块瓷砖的上面，前提是它比上一块瓷砖窄。Bongani可以将瓷砖旋转90度，使其宽度变成高度，高度变成宽度。他也可以完全丢弃一块瓷砖。给定一组瓷砖，请帮助Bongani找到他可以建造的最高瓷砖堆。例如，指定了瓷砖（3,3），（12,5），（5,8），（6,10）。为了获得最高的瓷砖堆，Bongani忽略了第一块瓷砖（3,3），因为它比下一块瓷砖小。他使用下一块瓷砖（12,5）作为宽度为12，高度为5。接下来，他使用两块8宽5高的瓷砖，然后是6宽10高的瓷砖。

我能想到的唯一办法就是获取所有可能的有效瓷砖排列，然后找到最高的排列。

具体问题可在此处找到 http://www.olympiad.org.za/olympiad/wp-content/uploads/2013/01/2011PO-R2-Questions-0421.pdf（第5题）。

- Tamir Shklaz

您明白我的回答了吗？还需要我解释些什么吗？ - aioobe

3个回答

2

以下是使用动态规划的二次时间复杂度算法。设f(i)为使用第i块木块在原始方向上且后续没有更多木块时可以建造的最大高度，g(i)则为使用第i块木块旋转之后且后续没有更多木块时可以建造的最大高度。需要注意的是可以省略一些木块，因此计算f(i)时必须在所有先前的f和g值兼容于该方向时取得最大值再加1；计算g(i)同理。最终答案为所有f(i)和g(i)中的最大值。

以下代码展示了f的代码。你可以编写类似的g函数，或修改此代码以接受另一个参数，表示木块i是否处于原始方向上。

public int f(int i)
{
    if (i == 0)
        return 1;
    if (memoF[i] > 0)
        return memoF[i];
    int maxFound = 1; // using just this block is legal
    for (int j = 0; j<i; j++){
        if (widths[i] < widths[j])
            maxFound = Math.max(f(j)+1,maxFound);
        if (widths[i] < heights[j])
            maxFound = Math.max(g(j)+1,maxFound);
    }
    memoF[i] = maxFound;
    return memoF[i];
}

- Douglas Zare

这个问题超出了我的能力范围 :/。你能不能尽量简单地解释一下呢？不过还是非常感谢你的回答。 - Tamir Shklaz

@TamirShklaz：第一步可能是更仔细地阅读问题陈述。从你关于尝试每个排列的评论来看，你似乎认为你可以重新排序瓷砖，但问题陈述中明确表示你不能这样做。因此，没有需要尝试的排列。你知道记忆化或动态规划是什么吗？ - Douglas Zare

我对动态规划有一些模糊的了解，但几乎不知道记忆化。你知道有关这方面的指南或教程吗？ - Tamir Shklaz

如果你在谷歌上搜索动态规划，你应该会在前几个搜索结果中找到以下内容：维基百科关于动态规划的页面以及CodeChef上的动态规划教程。请花些时间学习这一重要且基础的技术，这是竞赛编程中必须掌握的，否则你将无法理解这里给出的答案。 - Douglas Zare

0

我认为这是使用回溯法进行简单高效解决的典型例子。

你只需按顺序尝试可以做的第一件事情，如果无法继续，则返回并尝试之前未尝试过的事情。只需在Google上搜索“数独回溯法”，就有很多页面对此进行了解释。

回溯法在这种情况下的巨大优势在于，“削减”了许多没有意义的情景，因此比尝试检查每个可能的组合更有效。（例如在数独中，通过回溯法，大多数数独在1000-10000步内解决，这是相当不错的成绩，考虑到你可以写出的所有数字的可能组合约为10^60。）

- libik

你是在建议一个指数时间复杂度的算法？ - aioobe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aioobe · Accepted Answer

以下是动态规划解决方案的概述：

您需要“从左到右”移动，对于每个瓷砖，您需要确定以下内容：

- 使用此瓷砖未旋转时可以建造多高的塔楼 - 使用此瓷砖旋转后可以建造多高的塔楼 - 不使用此瓷砖可以建造多高的塔楼

第一个关键观察结果是，每个问题都可以通过递归方式回答（“如果根据当前选择更新当前宽度，则我可以为剩余瓦片建造多高的塔楼？”）。伪代码：

maxHeight(tiles, currentWidth) {

    // Base case
    if (tiles.isEmpty())
        return 0;  // no tiles -> maxHeight == 0

    int h = 0;
    currentTile = tiles[0]
    remainingTiles = tiles[1...]

    // Compute maxHeight for the case when not using current tile
    h = max(h, maxHeight(remainingTiles, currentWidth)

    // Compute maxHeight when using current tile
    if (currentWidth > currentTile.width)
        subHeight = maxHeight(remainingTiles, currentTile.width)
        h = max(h, subHeight + currentTile.height)

    // Compute maxHeight when using current tile rotated
    if (currentWidth > currentTile.height)
        subHeight = maxHeight(remainingTiles, currentTile.height)
        h = max(h, subHeight + currentTile.width)

    return h
}

第二个关键观察是许多对maxHeight的调用具有相同的参数，这意味着可以重复使用先前的计算。您可以使用备忘录或表格化（两者都是动态编程的变体）。如果您选择使用一个表格化矩阵，它看起来像这样：

M[tileN][width] = the height of the tower possible to build from
                  tileN onwards with width 'width'

正如你所注意到的那样，width没有明确的上限。在开始之前，可以将所有值映射到1、2、3、...以解决这个问题。然后最大宽度将是2N。