activity 选择的最优性证明
proof of optimality in activity selection
有人可以用不太正式的方式解释一下贪婪选择如何成为 activity 选择问题的最优解吗？这是我找到的最简单的解释，但我不太明白
How does Greedy Choice work for Activities sorted according to finish time?
Let the given set of activities be S = {1, 2, 3, ..n} and activities be sorted by finish time. The greedy choice is to always pick activity 1. How come the activity 1 always provides one of the optimal solutions. We can prove it by showing that if there is another solution B with the first activity other than 1, then there is also a solution A of the same size with activity 1 as the first activity. Let the first activity selected by B be k, then there always exist A = {B – {k}} U {1}.(Note that the activities in B are independent and k has smallest finishing time among all. Since k is not 1, finish(k) >= finish(1)).
以下是我对贪心解为什么总是词的理解：
断言：如果A是贪婪的选择（从排序数组中的第一个activity开始），那么它给出了最优解。
证明: 让我们有另一个选择 B 从一些 activity k (k != 1 or finishTime(k)>= finishTime(1 )) 单独给出最优 solution.So, B 没有 1st activity 并且下面的关系可以写在 A 和 [=12 之间=]可以写成：
A = {B - {k}} U {1}
此处：
1.Sets A 和 B 不相交
2.Both A 和 B 中有兼容的活动
由于我们得出|A|=|B|，因此activityA也给出了最优解
如果区间为 S={1,2,3,.....m} 并且解的长度为 n1，则假设 A 是从 1 开始的最优解。如果 A 不是最优解，则存在另一个解 B，它以 k!=1 和 finishTime(k)>=finishTime(1) 开头，长度为 n2。
所以，n2>n1。
现在，如果我们从解决方案 B 中排除 k，那么我们将剩下 n2-1 个元素。
由于 k 不与 B 中的其他区间重叠，因此 1 也不会重叠。
这是因为 B 中的所有区间（不包括 k）的 startTime>= finishTime(k)>=finishTime(1)。因此，如果我们将 B 中的 k 替换为 1，我们仍然有 n2 个长度。但是从 1 开始的最佳解决方案是长度为 n1 的 A。我们得到 n1=n2 ，这与 n2>n1 相矛盾。因此从1开始的解决方案是最优的。
有人可以用不太正式的方式解释一下贪婪选择如何成为 activity 选择问题的最优解吗？这是我找到的最简单的解释，但我不太明白
How does Greedy Choice work for Activities sorted according to finish time? Let the given set of activities be S = {1, 2, 3, ..n} and activities be sorted by finish time. The greedy choice is to always pick activity 1. How come the activity 1 always provides one of the optimal solutions. We can prove it by showing that if there is another solution B with the first activity other than 1, then there is also a solution A of the same size with activity 1 as the first activity. Let the first activity selected by B be k, then there always exist A = {B – {k}} U {1}.(Note that the activities in B are independent and k has smallest finishing time among all. Since k is not 1, finish(k) >= finish(1)).
以下是我对贪心解为什么总是词的理解：
断言：如果A是贪婪的选择（从排序数组中的第一个activity开始），那么它给出了最优解。
证明: 让我们有另一个选择 B 从一些 activity k (k != 1 or finishTime(k)>= finishTime(1 )) 单独给出最优 solution.So, B 没有 1st activity 并且下面的关系可以写在 A 和 [=12 之间=]可以写成：
A = {B - {k}} U {1}
此处：
1.Sets A 和 B 不相交
2.Both A 和 B 中有兼容的活动
由于我们得出|A|=|B|，因此activityA也给出了最优解
如果区间为 S={1,2,3,.....m} 并且解的长度为 n1，则假设 A 是从 1 开始的最优解。如果 A 不是最优解，则存在另一个解 B，它以 k!=1 和 finishTime(k)>=finishTime(1) 开头，长度为 n2。 所以，n2>n1。 现在，如果我们从解决方案 B 中排除 k，那么我们将剩下 n2-1 个元素。 由于 k 不与 B 中的其他区间重叠，因此 1 也不会重叠。 这是因为 B 中的所有区间（不包括 k）的 startTime>= finishTime(k)>=finishTime(1)。因此，如果我们将 B 中的 k 替换为 1，我们仍然有 n2 个长度。但是从 1 开始的最佳解决方案是长度为 n1 的 A。我们得到 n1=n2 ，这与 n2>n1 相矛盾。因此从1开始的解决方案是最优的。