如何使用动态规划实现活动选择问题(CLRS练习16.1-1)。我已经使用贪心算法实现了它,假设数组已经按完成时间排序,则运行时间为线性时间。
我知道它具有最优子结构。
令
我知道它具有最优子结构。
令
$S_{ij}$
表示在活动$a_i$
完成后开始并在活动$a_j$
开始之前完成的活动集。如果我们用$c[i j]$表示集合$S_{ij}$
的最优解大小,则我们将得到以下递推式。$c[i j] = c[i k] + c[k j] + 1$