活动安排最优子结构性怎么证明

活动安排问题是经典的动态规划问题，其中最优子结构性质可以通过以下方式证明：

假设我们有一个活动集合S={a1, a2, ..., an}，其中每个活动都有开始时间(start)和结束时间(finish)。

我们定义子问题为：对于活动集合S的子集S'，找到满足以下条件的最大活动子集A'：
1. A'是S'的一个合法活动子集，即每个活动都不会与其他活动发生时间冲突。
2. A'的活动数量最大。

现在，我们来证明最优子结构性质：

假设A是S的一个最大活动子集，其中最后一个活动是ak。我们可以将A划分为两部分：A1为A中在ak之前结束的活动子集，A2为A中在ak之后开始的活动子集。

如果A'是S'的一个最大活动子集，其中最后一个活动是ak'，我们也可以将A'划分为两部分：A1'为A'中在ak'之前结束的活动子集，A2'为A'中在ak'之后开始的活动子集。

我们可以观察到，A1是S中以ak为最后一个活动的最大活动子集，A1'是S'中以ak'为最后一个活动的最大活动子集。根据定义，A1和A1'都是最优的，因为它们都是各自问题的最优解。

根据上述分析，我们可以得出结论：对于任意活动集合S的子集S'，以及其中的任意一个活动ak'，如果我们知道了S'中以ak'为最后一个活动的最大活动子集A'，那么我们可以通过将A'与ak'相连接，得到S中以ak'为最后一个活动的最大活动子集A。

因此，我们可以得出结论：活动安排问题具有最优子结构性质。