多重背包的单调队列
物品数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]转移过来,只是样例恰好如此
加载不出图,试试科学上网
图炸了。
好家伙!图解竟没图
%%%%
加载不出来是之前用github做图床,现在已经移到gitee了。应该OK了
gitee由于内容审核、外链访问等压力不能做图床了。现在暂时改回github
试了一下,码云也不行。
直接上传到acwing啊
把 raw.githubusercontent.com/ 改成
raw.githubusercontents.com
佬我要图片QAQ
图片的网站崩了,来晚了,没了
想看图片
楼主麻烦你更新一下图片
图片看不了QAQ
皇帝的新图
图呢~~~
tql!!!!
图片看不了QAQ
写得这么好居然不是第一?
顶上去!
tql
tql