如何证明这个贪心算法是最优的？
How to prove this greedy algorithm as optimal?
问题听起来像这样：我们得到 n 个立方体。每个立方体都有长度（边的长度）和颜色。边的长度不同，但颜色不同，例如：任何两个立方体的长度永远不会相同，但颜色相同是可能的。颜色从1到p（给定p）。
我们必须按照以下规则建造一个具有最大高度的立方体塔：
1) 颜色相同的立方体无法叠加；
2) 立方体不能放在边长较小的立方体上
例如：立方体c1的长度为3，立方体c2的长度为5。立方体c1可以放在c2的上面，但是立方体c2不能放在c1的上面。
好吧，为了解决这个问题，我想出的算法是这样的：
- 我们按边长降序对立方体进行排序，然后将它们放入数组中；
- 我们将数组中的第一个立方体添加到塔中；
- 我们将最后插入的立方体的长度（在本例中为第一个立方体的长度）保存在变量 l 中；
- 我们将最后插入的立方体的颜色（在本例中为第一个立方体的颜色）保存在变量 c 中；
- 我们遍历数组的其余部分，插入第一个长度小于 l 且颜色不同于 c 的立方体，然后重复 3-4-5；
现在我遇到的困难是，如何证明这种贪心算法是最优算法？我想证明必须以某种方式看起来像这里的证明：http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf
问题是：
- 是否存在选择最大长度立方体不是最优的情况？
在每个决策节点，我们必须决定是选择 a 还是 b，给定 a>b :
假设选择 b 是严格最优的（意味着最大高度）:
- 案例一：
col(a) == col(b)
b optimal => final tower: b, x0, x1, ...- 但通过等高构造也有效：
a, x0, x1, ...
- 有效，因为：
col(a) == col(b)、(a > b) & (b > x0) => (a > x0)（传递性）
矛盾！
案例二 col(a) != col(b)
b optimal -> final tower: b, x0, x1, ...- 还有更高高度的有效构造：
a, b, x0, x1, ...
- 有效因为：
(a > b) & (col(a) != col(b)) => a before b
- 矛盾！
我们假设选择 b 是严格最优的并且显示出矛盾。选b只能和选a一样好或差（剩下的最大长度的立方体）。
问题听起来像这样：我们得到 n 个立方体。每个立方体都有长度（边的长度）和颜色。边的长度不同，但颜色不同，例如：任何两个立方体的长度永远不会相同，但颜色相同是可能的。颜色从1到p（给定p）。
我们必须按照以下规则建造一个具有最大高度的立方体塔：
1) 颜色相同的立方体无法叠加；
2) 立方体不能放在边长较小的立方体上
例如：立方体c1的长度为3，立方体c2的长度为5。立方体c1可以放在c2的上面，但是立方体c2不能放在c1的上面。
好吧，为了解决这个问题，我想出的算法是这样的：
- 我们按边长降序对立方体进行排序，然后将它们放入数组中；
- 我们将数组中的第一个立方体添加到塔中；
- 我们将最后插入的立方体的长度（在本例中为第一个立方体的长度）保存在变量 l 中；
- 我们将最后插入的立方体的颜色（在本例中为第一个立方体的颜色）保存在变量 c 中；
- 我们遍历数组的其余部分，插入第一个长度小于 l 且颜色不同于 c 的立方体，然后重复 3-4-5；
现在我遇到的困难是，如何证明这种贪心算法是最优算法？我想证明必须以某种方式看起来像这里的证明：http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf
问题是：
- 是否存在选择最大长度立方体不是最优的情况？
在每个决策节点，我们必须决定是选择 a 还是 b，给定 a>b :
假设选择 b 是严格最优的（意味着最大高度）:
- 案例一：
col(a) == col(b) b optimal => final tower: b, x0, x1, ...- 但通过等高构造也有效：
a, x0, x1, ... - 有效，因为：
col(a) == col(b)、(a > b) & (b > x0) => (a > x0)（传递性） 矛盾！
案例二
col(a) != col(b)b optimal -> final tower: b, x0, x1, ...- 还有更高高度的有效构造：
a, b, x0, x1, ... - 有效因为：
(a > b) & (col(a) != col(b)) => a before b - 矛盾！
我们假设选择 b 是严格最优的并且显示出矛盾。选b只能和选a一样好或差（剩下的最大长度的立方体）。