首先说一些写本文时的悲惨经历,一开始我是使用Gridea,编辑也是用它的编辑器,但是,在一次写作中,电脑无征兆地蓝屏了。我重启之后发现md文件打不开了,查看了一下二进制全是0 emmm(编写过程中保存了!!)。自此我换成了hexo emmm。
符号定义
首先我们定义一些符号,物品个数为 ,
第 个物品的体积为 ,价值为 , 最多为 个。
背包的体积为 ,动归数组为 .
回顾
我们先回顾多重背包的优化,( 是 背包体积为 时,背包能够承受的最大个数,即 )
设此时第 个物品的体积为 .
1 | dp[i, j]= max(dp[i - 1, j], dp[i - 1, j - v] + w, dp[i - 1, j - 2v] + 2w, ......,dp[i - 1, j - (x - 1) v] + (x - 1)w, dp[i - 1, j - xv] + xw) |
然后我们来思考,完全背包时, 和 的联系
1 | dp[i, j - v]= max(dp[i - 1, j - v], dp[i - 1, j - 2v] + w, dp[i - 1, j - 3v] + 2w, ......, dp[i - 1, j - (x - 1) v] + (x - 2)w, dp[i - 1, j - xv] + (x - 1)w) |
(有的同学可能会问最后一个背包能承受的数量为什么还是 ,但其实那不是 ,是 $ j-v-(\frac{j-v}{v})v$ 算出来状态最终减的是 )
然后我们惊奇地发现, 第一项之后的 和 是如此的相似,只差了个 ,所以我们可以把 移出来,替换成
1 | dp[i, j]= max(dp[i - 1, j], dp[i][j - v] + w) |
否定
然后我们来看多重背包,我们还推柿子看看(我们先假设此时 远大于 )
我们先尝试能否用完全背包的方法来优化,
1 | dp[i, j]= max(dp[i - 1, j], dp[i - 1, j - v] + w, dp[i - 1, j - 2v] + 2w, ......,dp[i - 1, j - (s - 1) v] + (s - 1)w, dp[i - 1, j - sv] + sw |
1 | dp[i, j - v]= max(dp[i - 1, j - v], dp[i - 1, j - 2v] + w, dp[i - 1, j - 3v] + 2w, ......, dp[i - 1, j - (s - 1) v] + (s - 2)w, dp[i - 1, j - sv] + (s - 1)w) |
看起来似乎很对,是吗?(
但是我们考虑一下项数,我们会发下 的项数 和 相同,都是 项 ,不和 第一项之后的 项数相同,从而不能使用之前的方法优化
展新
(从这一小节开始用一维数组,方便表示,没学过一维数组表示的去学一下 )
我们还是考虑 ,还是列柿子
1 | dp[j]= max(dp[j], dp[j - v] + w, dp[j - 2v] + 2w, ......,dp[j - (s - 1) v] + (s - 1)w, dp[j - sv] + sw |
我们观察这个柿子,很容易得出一个性质,会更新状态 的状态和 都是模 意义下同余的。于是我们把状态 到 划分成 类,分别是模 余 的,模 余 的,,模 余 的,以及模 余 的。
原来的dp[1]~dp[V]
我们就可以变化成这 类(这里比较难想,但一定要想明白)
1 | dp[0] dp[v] dp[2v] dp[3v] ... dp[kv] |
然后我们就可以在这 类分别更新了。(其中 为恰好满足最后一个状,看代码)
写一下这样的代码(先写一个二维的)(如果改为一维要倒序枚举状态或利用滚动数组)
1 | for(int i = 1;i <= n;i++) |
对,你没有看错,这是四层循环,也许你要问了,这循环怎么还越搞越多了,但是让我们分析一下他的时间复杂度。第一层循环 ,第二层循环是枚举每一类的起始值的,第三层是枚举该类里每一个状态的,二三层的总共时间复杂度是 ,最后一层就是枚举 可以转移到当前状态的状态,是 的,所以总共时间复杂度还是 的。
如果上面没明白我们举个例子。
举个例子吧,假设有 件物品,,,,,,,背包体积为
在 即枚举第一个物品的时候,dp状态的分类为
1 | dp[0] dp[5] dp[10] dp[15] dp[20] dp[25] dp[30] |
1 | //第一(余数为0)的一类 |
也一样
单调队列优化
也许你要问了,说了这么多怎么连单调队列的影子都没看见,其实我们之前做的都是为了ta做铺垫,ta这不就来了。
首先,我们要优化的就是上面的代码的第四层:由当前状态的前面 个(不相邻的,每两个相差 )状态来更新当前状态。
我们从感性地角度来思考一下,上图!(qwq
我们来看这个图, 这里表示的就是当前状态 ,表示的是下一个状态 即 ,灰色格子表示的是 ***可以更新当前状态(这里为 或 )*的状态
!!!!!注意:图片里第一行最左面的应该是 手贱写错了(懒得改了emmm)
我们可以观察出来,状态每增加 ta的式子dp[j]= max(dp[j], dp[j - v] + w, dp[j - 2v] + 2w, ......,dp[j - (s - 1) v] + (s - 1)w, dp[j - sv] + sw
就会失去最后(图上最左)面的一个 可以更新ta的状态 ,同时也得到了最前(图上最右)面的一个 可以更新ta 的状态。
让我们思考一下,可以在两端插入(因为 每次增加 ,max函数每就会多一个可用来更新 当前状态 的状态),删除数据(也会少一个),并支持较小 ()的时间复杂度求最大值(为max函数要求)的数据结构是什么?单调队列!(单调队列里存的是下标,而不是具体数据)
一些小细节
偏移量
1 | dp[0] dp[v] dp[2v] dp[3v] ... dp[kv] |
我们把类的起点(指dp[0]
到dp[v-1]
),随便选一个,设为 来看。
1 | dp[u] = dp[u] |
我们发现在max函数里,dp[] 后面加的值不一样,这就很难受,我们在单调队列里更新值很不方便,所以我们搞点花样。
1 | dp[u] = dp[u] |
这样看起来就很舒服了。每次进单调队列的值就是dp[u + kv] - k*w
。更新当前状态的时候最后别忘了加上 ,a就是 。为什么呢,我们来看一看
我们知道,队首dp[u + kv] - k*w
为 固定, 在范围内任意取得的最大值。我们在更新当前状态(假设为 )的时候 ,max函数外的偏移量为 正的 ,而dp[u + kv]
比dp[u + kv] - k*w
少减了 ,而最后max函数外又要给ta加上 ,所以综合下来就是加上 也就是
队列里个数应为 个,为 到 个 前面状态
滚动数组
前面提到过,多重背包要么倒序枚举,要么滚动(备份)数据,但单调队列的性质来看,倒序枚举不太方便,所以我们采用备份数组的方式
代码
然后我们就可以愉快地敲代码了
1 |
|
完结撒花!