最近做算法题,多重背包的单调队列看了几遍闫学灿同学的视频讲解没看懂,自己总结了一下。
多重背包的单调队列
物品数n=3,背包空间v=11
计算过程与转移公式
dp[i][j]代表只考虑前i个物品, 背包容量为j时, 可获得的最大价值
转移公式:dp[i][j] = max(dp[i-1][j], dp[i-1][j-kc] +kw), 1≤k≤s = max(dp[i-1][j-kc] +kw) , 0≤k≤s
转移表如下:
只考虑求dp[2][1]时
绿色代表:背包容量v % 物品空间c = 0
橙色代表:背包容量v % 物品空间c = 1
绿色只从上一层绿色更新,橙色只从上一层橙色更新
只考虑绿色块的转移过程
绿色代表有效区域,灰色代表无效区域(由于只能向后转移,或者物品个数限制)。物品个数限制也可以理解为每行最多有s+1个元素。
黑色字体代表该行最大值
上图这个过程可以通过单调队列实现
另一种角度看转移过程
虚线代表物品个数限制导致的无效的转移
实线代表有效的转移
红色代表最大值那条转移
得到结果
完全背包问题的另一种角度
完全背包问题转移图和多重背包一样。不过没有了物品个数限制,所以不是滑动窗口情况,不用单调队列。只保存一个最大值就可以。
不一定全由dp[1][0]转移过来,只是样例恰好如此
参考目录
https://www.zybuluo.com/RabbitHu/note/857837