前段时间遇到个完全背包问题,于是看了DD牛的背包九讲,对于01背包和完全背包还好理解,不过对于多重背包我一直理解的不是很透彻,尤其是那个复杂度,我一直认为是O(N*V*Σ(log(n[i])))的,但是DD牛的九讲上说是O(V*Σ(log(n[i])),这个复杂度确实是DD牛讲的那个,表示一开始我想错了。还有就是可以用单调队列优化达到O(N*V),于是上网搜了好多报告,无奈实在不懂。后来问了王向,他说不用单调队列也可以达到O(N*V)的,给了我个网址。昨天下午就学些了下。发现还比较好懂。今天上午就依着那个思路把1014和1742给写了,发现还可以速度不错。
附上1014的带注释代码