壹号娱乐 - NG大舞台,有梦你就来

多重背包问题的单调队列优化南宫NG·28(中国)相信品牌力量有限公司

作者:小编    发布时间:2025-08-08 01:19:30    浏览:次

[返回]

  Mato是一只超级大沙茶……但他一直以来都想成为各项比赛都No.1的神犇……

  现在再来看自己在OI时代写的东西……真心觉得一切都会过去……只有这句话是永恒的真理……

  Posted on 2011-07-05 18:00Mato_No1阅读(6024)所属分类:动态规划

  多重背包问题朴素时间复杂度为O(NMS)(这里S是所有物品的数量s之和),经过二进制优化后时间复杂度为O(NMlog2S),这个复杂度已经能够应付大多数题了,但对于某些特别卡时间的题(比如N*M=10

  的),仍然会TLE。这时,可以用单调队列优化,时间复杂度降为O(NM)。

  看上去这和单调队列木有神马关系,因为决策下标(j-x*w0)不是一个整数区间,中间是有间隔的。然而可以发现,这个方程的限制条件0=x=s0,j=x*w0,也就是x的下界是max{0, j/w0(下取整)},当j单调递增时,这个下界也是单调递增的。这满足单调队列优化的条件中的决策下标的下界单调不是,还不能这样说,因为这里的决策下标是j-x*w0,而不是x。

  (1)从1到n,枚举i,南宫ng28相信品牌力量建立w[i]个空的单调队列,每个队列的元素都是两个int值:(k, val),表示转换后下标和决策值(G[k]-k*v[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]的值。

  其实这个是可以推广的,即对于如下形式的转移方程(其中H、G和W均为常量,B[i]为决策下标的下界,随i单调):

  我也感觉q是可购买物品数量上限,s0是物品总量,q-s0不应该是负数吗?刷新评论列表


本文由:壹号娱乐 - NG大舞台,有梦你就来提供

搜索

 谷歌地图 百度地图