前段時間遇到個完全背包問題,于是看了DD牛的背包九講，對于01背包和完全背包還好理解，不過對于多重背包我一直理解的不是很透徹，尤其是那個復雜度,我一直認為是O(N*V*Σ(log(n[i])))的，但是DD牛的九講上說是O(V*Σ(log(n[i]))，這個復雜度確實是DD牛講的那個,表示一開始我想錯了。還有就是可以用單調隊列優化達到O(N*V),于是上網搜了好多報告,無奈實在不懂。后來問了王向，他說不用單調隊列也可以達到O(N*V)的,給了我個網址。昨天下午就學些了下。發現還比較好懂。今天上午就依著那個思路把1014和1742給寫了，發現還可以速度不錯。
附上1014的帶注釋代碼