algorithm - 用立方体 build 一座塔

Question

您可以通过不将较大的立方体放在较小的立方体上而将立方体制成稳定的塔，也不能将较重的立方体放在较轻的立方体上。

编写一个程序，从 N 个立方体中找出最高的塔。

输入文本的第一行包含立方体的数量。 (1<=n<=100) 后面N行是立方体的长度和重量。

例子:

Input.txt       Output.txt (from bottom to top)
5               3
10 3            20 5
20 5            10 3
15 6            10 2
15 1
10 2

内存限制:16 mb 运行时间:0.2 秒

你能帮帮我吗？

Answer 1

算法

我想出的算法通过使用有序对列表来工作。这些对首先按一个元素排序，然后按第二个元素排序。

我们维护对列表，其中每个新对是:

• 添加到最高列表的末尾，如果它可以放在最后一个元素之后
• 添加到新列表的末尾，该列表是现有列表之一中找到的最高段的副本，可以将其附加到该列表中
• 如果现有列表中的任何地方都放不下，则将其添加到新列表中。

---

证明

1. 第一个元素将进入一个新列表，然后它将是最高的。
2. 第 n 个元素将到达最高列表(或列表段)的末尾，使其成为包含该元素的最高列表。
3. n 之后的第一个元素，元素 k，可以使用 附加到列表>n 将附加到包含 n 的最高列表，因为 2。如果某个更高的列表存在元素 < strong>i 元素 k 可以附加到哪个元素 k，然后规则 2 应用于元素 i 。这使得具有 k 的列表成为具有该元素的最高列表。

通过归纳，这证明了算法的概念。

---

伪代码

foreach ordered pair
    maximumIndex <- 0
    maximumList <- null
    foreach list
        highest, length <- FindLongestPath(list, pair)
        if highest > maximumHeight
            maximumHeight<- highest 
            maximumIndex <- lenght
            maximumList <- list
    if maximumIndex = 0
        lists.add(new list{pair});
    else if maximumIndex < maximumList.Length
        lists.add(new list{maximumList[0..maximumIndex - 1] + pair});
    else
        list.add{pair};

FindLongestPath 方法在列表中搜索该对可以放入的第一个位置，并返回该段的高度。对于一个简单的应用程序(for 从一开始直到找到位置)，我估计算法的复杂度在最坏的情况下为 O(N^2)。

如果实现为二分查找，我猜复杂度为 O(N log N)，但对于 N <= 100，这并不重要。

---

实际代码

因为没有人喜欢破译其他人的伪代码，这里是 pastebin 上实际工作的 C# 代码:http://pastebin.com/3vLn343j

文件“Input.txt”的格式与问题中的一样，应该与可执行文件位于同一目录中(在 Visual Studio 中，您可以将其放在解决方案根目录中，并在属性中将“复制到输出”设置为“如果较新，请复制')。