用python实现带权活动安排问题基于动态规划算法
发布时间
阅读量：
阅读量
动态规划主要有两种具体实施途径，在算法设计中我们通常会遇到两种主要的方法：一种是采用递归策略来解决问题其中这种方法虽然直观但可能会导致较高的时间复杂度；另一种方法则是自底向上的迭代方式这种逐步构建结果的方式不仅能够有效降低算法的时间复杂度还能提高程序运行效率因此在实际应用中我们需要根据具体情况选择合适的方法以确保算法的高效性
首先我们描述带权活动安排问题的相关内容并阐述解决该问题的具体步骤
问题：考虑一组活动，在每个活动中都有一个开始时间和结束时间s和f，并且每个活动带来一定的收益w。当且仅当si≥fj时（即si≥f_j），活动i与j是相容的。
目标 ：找到一个活动子集，使得子集中的活动相互兼容，并且收益最大。
解析：
其中OPT(j)表示从包含编号为1到j的所有活动中选出一组互不相交的收益最大的总和。
p(j)定义为在活动集合{1,2,…,j-1}中与活动j兼容的那些活动的最大索引值。
对于每一个特定的活动j来说，在动态规划过程中有两种决策方式：要么选择执行该活动并将其带来的收益wj与其之前的兼容子集最优解相结合；要么放弃执行该活动而继承到前一个不冲突的最优解。
转移方程为：
还没有任何评论哟~