堆叠瓷砖（硬算法） [英] Stacking Tiles (Hard algorithm)

问题描述

这是从code竞争的问题，我发现它令人难以置信的困难拿出任何有效的算法来解决它。所以我没有真正寻找的code，而是如何解决它一步步的算法。

This is a question from a code competition, I am finding it unbelievably difficult to come up with any working algorithm to solve it. So I'm not really looking for the code but rather a step by step algorithm on how to solve it.

堆叠瓷砖靠墙是邦哈尼的最爱pasttimes之一。他的砖都具有相同的厚度，但不一   在宽度和高度。邦哈尼是指定N瓷砖和具有使用它们中   根据一组规则给出的序列。他可以把瓷砖   另一个之上，只有当它是比previously层叠窄   瓦。邦哈尼允许90度，以便以旋转瓦片   宽度变高度和高度变宽度。他也被允许   完全丢弃的瓷砖。由于瓷砖的名单，帮助邦哈尼找到   他可以建造的例子最高的堆栈指定瓷砖（3,3），   （12，5），（5,8），（6,10）。为了获得最高的堆栈邦哈尼忽略   第一瓦片（3，3），因为它是比下一个瓦片小。他用   下一瓦片（12 5）与12的宽度和5作为高度。他用   接下来的两个瓷砖8作为宽度和5作为高度后跟   6作为宽度和10的高度。

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）

The only thing I can possibly think of is getting every possible valid permutation of tiles and find the highest permutation. The exact question can be found here http://www.olympiad.org.za/olympiad/wp-content/uploads/2013/01/2011PO-R2-Questions-0421.pdf (Question 5)

推荐答案

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

Here's an outline of dynamic programming solution:

您移动从左至右，并为每个你找出瓷砖

You "move from left to right" and for each tile you figure out

• 如何高台，我可以通过建的使用这种瓷砖未旋转​​的
• 在我有多高的塔可以通过建立的使用这种瓷砖旋转的的
• 在我有多高的塔可以通过建立的不使用的这种瓷砖

• how high tower can I build by using this tile unrotated
• how high tower can I build by using this tile rotated
• how high tower can I build by not using this tile

第一个关键的观察是，每一个问题都可以递归地回答（我有多高的塔可以建立对剩余的瓷砖，如果当前宽度是根据我目前的选择更新？）。伪code：

The first key observation is that each question can be answered recursively ("how high tower can I build for the remaining tiles if the current width is updated according to my current choice?"). Pseudo code:

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 的调用都具有相同的参数，这意味着previous计算可以重复使用。您可以使用记忆化或制表（两者都是动态规划的变体），如果您选择使用制表矩阵，它是这样的：

The second key observation is that many of the invocations of maxHeight have the same arguments, which means that previous computations can be reused. You can either use memoization or tabulation (both are variants of dynamic programming) If you choose to use a tabulation matrix, it would look like this:

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

（正如您可能注意到宽度并没有一个明确的上限，这可以通过映射所有值要解决 1，2，3 ...... 开机前，最大宽度届时将2N。）

(As you may note width does not have a clear upper bound. This can be solved by mapping all values to 1, 2, 3, ... before starting. Maximum width will then be 2N.)

这篇关于堆叠瓷砖（硬算法）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！