algorithm - 如何证明这个贪心算法是最优的？

Question

问题听起来像这样:我们得到 n 个立方体。每个立方体都有长度(边的长度)和颜色。边的长度不同，但颜色不同，例如:任何两个立方体的长度永远不会相同，但颜色相同是可能的。颜色从 1 到 p(给定 p)。

我们必须按照以下规则 build 一个具有最大高度的立方体塔:

1) 如果立方体的颜色相同，则不能将它们放在立方体之上；

2) 立方体不能放在边长较小的立方体上。

例如:立方体c1的长度为3，立方体c2的长度为5。立方体c1可以放在c2的顶部，但立方体c2不能放在c1的顶部。

好吧，为了解决这个问题，我想出的算法是这样的:

1. 我们按边长降序对立方体进行排序，然后将它们放入一个数组中；
2. 我们将数组中的第一个立方体添加到塔中；
3. 我们将最后插入的立方体的长度(在本例中为第一个立方体的长度)保存在变量 l 中；
4. 我们将最后插入的立方体的颜色(在本例中为第一个立方体的颜色)保存在变量 c 中；
5. 我们遍历数组的其余部分，插入第一个长度小于 l 且颜色不同于 c 的立方体，然后重复 3-4-5；

现在我遇到的困难是，如何证明这种贪心算法是最优算法？我想证明必须以某种方式看起来像这里的那些:http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf

Answer 1

问题是:

• 是否存在选择最大长度立方体不是最优的情况？

在每个决策节点，我们必须决定是选择a还是b，给定a>b:

假设选择 b 是严格最优的(意味着最大高度):

• 案例 1: col(a) == col(b)
• b optimal => final tower: b, x0, x1, ...
• 但通过等高构造也有效:a, x0, x1, ...
• 有效因为:col(a) == col(b), (a > b) & (b > x0) => (a > x0) (传递性)

• 矛盾!

• 案例 2 col(a) != col(b)

• b 最优 -> 最终塔:b, x0, x1, ...
• 还有更高高度的有效结构:a, b, x0, x1, ...
• 有效因为:(a > b) & (col(a) != col(b)) => a before b
• 矛盾!

我们假设选择 b 是严格最优的并且显示出矛盾。选择 b 只能与选择 a(剩余的最大长度立方体)一样好或差。