多重背包问题的单调队列优化

Posted on 2011-07-05 18:00 Mato_No1 阅读(5395) 评论(3)  编辑 收藏 引用 所属分类: 动态规划
多重背包问题朴素时间复杂度为O(NMS)(这里S是所有物品的数量s之和),经过二进制优化后时间复杂度为O(NMlog2S),这个复杂度已经能够应付大多数题了,但对于某些特别卡时间的题(比如N*M=107的),仍然会TLE。这时,可以用单调队列优化,时间复杂度降为O(NM)。

首先看一下多重背包问题的朴素转移方程:
F[i][j] = max{F[i-1][j-x*w[i]]+x*v[i]} (0<=x<=s[i], j>=x*w[i])
如果使用滚动数组,忽略i这一维,设w0=w[i],v0=v[i],s0=s[i],得:
F[j] = max{F[j-x*w0]+x*v0} (0<=x<=s0, j>=x*w0)
看上去这和单调队列木有神马关系,因为决策下标(j-x*w0)不是一个整数区间,中间是有间隔的。然而可以发现,这个方程的限制条件“0<=x<=s0,j>=x*w0”,也就是x的下界是max{0, j/w0(下取整)},当j单调递增时,这个下界也是单调递增的。这满足单调队列优化的条件中的“决策下标的下界单调”……不是,还不能这样说,因为这里的决策下标是j-x*w0,而不是x。
那么怎样才可以把决策下标变为x?

将决策下标按照模w0的余数进行分类,可以分成w0类,分别对应模w0余0、余1……余(w0-1)的情况。这时,上面方程中的所有决策下标j-x*w0都是同一类的。进一步,设q =j/w0(下取整),r=j%w0,则j=q*w0+r,对于某个决策下标j',设k=(j'-r)/w0,即j'=k*w0+r。显然可以发现,k的取值范围是:k>=0且q-s0<=k<=q,也即k的下界是max{0, q-s0}——随j的单调而单调。
然后,转移方程可以改为(这里把r当成一个已知量了):
F[q*w0+r] = max{F[k*w0+r]+(q-k)*v0} (k>=0且q-s0<=k<=q)
即F[q*w0+r]=max{F[k*w0+r]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
设G[k]=F[k*w0+r]得:
G[q]=max{G[k]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
这个方程已经可以使用单调队列来优化了!

这样可以得出算法:
(1)从1到n,枚举i,建立w[i]个空的单调队列,每个队列的元素都是两个int值:(k, val),表示转换后下标和决策值(G[k]-k*v[i]);
(2)从0到m,枚举j,得出q、r的值,对于队列r:
【1】删去队首过时(k<q-m[i])的元素;
【2】F[j]入队(这里的F[j]指上一阶段的F[j],即F[i-1][j]。因此这一步操作一定要先进行),删去队尾所有决策值val不大于(F[j]-q*v[i])的元素。
【3】取出队首结点,其val值加上q*v[i]后即为本阶段F[j]的值。
最后F[m]即为结果。总时间复杂度为O(NM)。

其实这个是可以推广的,即对于如下形式的转移方程(其中H、G和W均为常量,B[i]为决策下标的下界,随i单调):
F[i] = opt{F[i-x*H+W]}+G (B[i]<=i-x*H+W<i,x∈N
都可以用上述的办法进行转化,从而进行单调队列优化。

Feedback

# re: 多重背包问题的单调队列优化  回复  更多评论   

2014-05-03 19:13 by gga
k的取值范围是:k>=0且q-s0<=k<=q ;q-s0<=k是为什么

# re: 多重背包问题的单调队列优化  回复  更多评论   

2014-05-03 22:49 by gga
”然而可以发现,这个方程的限制条件“0<=x<=s0,j>=x*w0”,也就是x的下界是max{0, j/w0(下取整)}“ 这个下界不对吧,是你所想的理想情况(j<=x*w0)吧?

# re: 多重背包问题的单调队列优化  回复  更多评论   

2014-05-09 20:37 by zzhhbyt
@gga
我也感觉q是可购买物品数量上限,s0是物品总量,q-s0不应该是负数吗?

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理