堆叠瓷砖（硬算法）

Question

这是一个代码竞赛的问题，我发现很难想出任何可行的算法来解决它。所以我并不是真的在寻找代码，而是在寻找如何解决它的分步算法。

Stacking Tiles

Stacking tiles against the wall is one of Bongani's favourite pasttimes. His tiles all have the same thickness, but vary in width and height. Bongani is given N tiles and has to use them in the sequence given according to a set of rules. He can place a tile on top of another only if it is narrower than the previously stacked tile. Bongani is allowed to rotate the tiles by 90 degrees so that width becomes height and height becomes width. He is also allowed to discard a tile altogether. Given a list of tiles, help Bongani find the highest stack he can build The example specifies tiles (3, 3), (12, 5), (5, 8), (6, 10). To get the highest stack Bongani ignores the first tile (3, 3) as it is smaller than the next tile. He uses the next tile (12, 5) with 12 as the width and 5 as the height. He uses the next two tiles with 8 as the width and 5 as the height followed by 6 as the width and 10 as the height.

我唯一能想到的就是获取所有可能的有效排列并找到最高排列。可以在此处找到确切的问题 http://www.olympiad.org.za/olympiad/wp-content/uploads/2013/01/2011PO-R2-Questions-0421.pdf（问题 5）

Answer 1

我认为这是使用回溯法轻松有效求解的典型示例。

你只要按顺序尝试你能做的第一件事，当你不能继续的时候，你就回去尝试你之前没有尝试过的那个。只是 google "Sudoku Backtracking" 有很多页面解释了这一点。

在这种情况下回溯的巨大优势在于，它 "cuts" 关闭了很多没有意义的场景，因此它比尝试检查每个可能的组合更有效。（就像在数独游戏中一样，通过回溯，大多数数独游戏在 1000-10000 步内解决，这非常好，因为您可以写出所有可能的数字组合是 ~10^60）

Answer 2

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

你 "move from left to right" 并且你找出每个方块

我可以使用这个未旋转的方块
我可以使用这个旋转的方块
我可以不使用这个方块

第一个关键观察是每个问题都可以递归回答 ("how high tower can I build for the remaining tiles if the current width is updated according to my current choice?")。伪代码：

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。）

Answer 3

这是一个使用动态规划的二次时间算法。设 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];
}

堆叠瓷砖（硬算法）

Stacking Tiles (Hard algorithm)

java

sorting

algorithm

graph

permutation

Stacking Tiles