16.1-5
這題實際是帶權的活動求取最大權重的活動選擇問題，使用動態規劃求解。如果有心學好的動態規劃的同學可以去 “ B站上搜 ’ 動態規劃（第1講） ‘，選擇作者是：正月點燈籠的視頻 ” 看看，他的這個視頻講解的就是這個問題的求解，簡單易懂。
答案：
首先，活動集中的活動已經按照結束時間先后順序進行了排序；
其次，定義兩個數組R[1…n]；pre[1…n] （其中，n為活動集的規模）。R[]數組存放的是權重和的最大值，例如R[j]表示j活動及其之前活動的權重和的最大值；pre[i]數組存放的i活動前面與i活動兼容的且最鄰近的活動。
最后，就是選擇問題。（1）如果選當前的活動，那么就是該活動的權值加上與該活動之前的兼容的活動權重；（2）如果不選當前活動，那么就是求解該活動的下一個活動，執行（1）操作

可以寫出遞推式：

偽代碼如下：

總結

以上是生活随笔為你收集整理的算法导论第三版 16.1-5习题答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。