多重背包问题 III(滑动窗口细节+举例图解+式子感受=顿悟)
姐妹篇:解读lys大佬解读yxc的代码的代码
https://www.acwing.com/solution/content/92979/
自己捣鼓了不少时间,特此记录。
前置知识:多重背包的原始状态转移方程
$ f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,⋯,f(i−1,j−sv)+sw)$
下面我们以$s = 3, j = 5v + r$为例子,这是一个比较舒服的长度。
式子表示
我们首先从上往下写:
$ f(i, j) = \max (f(i-1, j), f(i - 1, j - v) + w),f(i - 1, j - 2v) + 2w,f(i -1,j - 3v) + 3w) $
$ f(i, j - v) = \max (f(i - 1, j - v),f(i - 1, j - 2v) + w,f(i - 1, j - 3v) + 2w, f(i - 1, j - 4v) + 3w)$
$ f(i, j - 2v) = \max (f(i - 1, j - 2v),f(i - 1, j - 3v) + w, f(i - 1, j - 4v) + 2w, f(i - 1, j - 5v) + 4w) $
$ f(i, j - 3v) = \max (f(i - 1, j - 3v),f(i - 1, j - 4v) + w, f(i - 1, j - 5v) + 2w) $
$ f(i, j - 4v) = \max (f(i - 1, j - 4v),f(i - 1, j - 5v) + w) $
$f(i, j - 5v) = f(i - 1, j - 5v) = f(i - 1, r)$
让我们改写一下,去掉所有的$i - 1$,用余数的形式表示,方便后面说明
我们会发现等号右侧的右侧的项数都是小于4的几项之和,这就是“滑动窗口”框住的几项
滑动窗口
这张图其实有一定的误导性,需要明确以下几点。
-
$f(i,j - kv),k = 0,1,2,..s[i]$的值不能像完全背包问题一样,由同维度$f(i,…)$的其它值推出,故轴上的值与$f(i, …)$无关
-
窗口不是在一条固定的轴上滑动,即这条轴的值会改变
-
窗口是在$f(i - 1, j - kv) + 偏移量, k = 0,1,2,..s[i]$这条“轴”上滑动。
图解
下面是根据我的理解画出的图
以第二行为例,第二行的含义是
$ f(i, j - v) = \max (f(r + 4v),f(r + 3v) + w,f(r + 2v) + 2w, f(r + v) + 3w),其中j - v = r + 4v$
可以看到有一个窗口“探出头来”,然后向右移动,(某种程度上来说也在向上滑动),长度最大为4,这就是我们的“滑动窗口”!
它每次是在一行的几个颜色块中取最大值。
参考文章:
https://www.acwing.com/solution/content/6500/
https://www.acwing.com/solution/content/53507/
https://www.acwing.com/solution/content/1537/
图很厉害,谢谢