大家好，欢迎来到IT知识分享网。
16.1-5
这题实际是带权的活动求取最大权重的活动选择问题，使用动态规划求解。如果有心学好的动态规划的同学可以去 “ B站上搜 ’ 动态规划（第1讲） ‘，选择作者是：正月点灯笼的视频 ” 看看，他的这个视频讲解的就是这个问题的求解，简单易懂。
答案：
首先，活动集中的活动已经按照结束时间先后顺序进行了排序；
其次，定义两个数组R[1…n]；pre[1…n] （其中，n为活动集的规模）。R[]数组存放的是权重和的最大值，例如R[j]表示j活动及其之前活动的权重和的最大值；pre[i]数组存放的i活动前面与i活动兼容的且最邻近的活动。
最后，就是选择问题。（1）如果选当前的活动，那么就是该活动的权值加上与该活动之前的兼容的活动权重；（2）如果不选当前活动，那么就是求解该活动的下一个活动，执行（1）操作
可以写出递推式：
伪代码如下：
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/12243.html
