java - 堆叠瓷砖(硬算法)

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

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

您“从左向右移动”并且对于您找出的每个方 block

• 使用未旋转的瓷砖我可以 build 多高的塔
• 使用这个旋转的瓷砖我可以 build 多高的塔
• 不使用这 block 砖我能建多高的塔

第一个关键观察是每个问题都可以递归地回答(“如果根据我当前的选择更新当前宽度，我可以为剩余的瓷砖 build 多高的塔？”)。伪代码:

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