单调队列优化的DP

（持续更新中……）

一、浅谈单调队列之多重背包

        前言：首先标题起了一个很优雅的名字，貌似很高深的样子，其实不然，只是把自己理解的记录一下而已。

    多重背包的状态转移方程：dp[ i ]  [ j ]  =  max ( dp[ i - 1 ] [ j ]  , dp[ i - 1 ] [ j - k * v[ i ] ] + k * w[ i ]  } (  0 <= k <= num[ i ])  ; 

先说一下多重背包的二进制解法，因为大多数的题目都可以用此方法解决：复杂度( num[ i ] 为每类物品的个数)。

  

   

    

     

    
    

     

      void Multip(int v ,int w ,int n) // v 为体积，w 为价值 ，n 为个数
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i = 1 ;i <= n ;i <<= 1) 
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       V[num] = i*v ;
     
    
   

    

     

    
    

     

       W[num++] = i*w ;
     
    
   

    

     

    
    

     

       n -= i ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(num)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       V[num] = i*v ;
     
    
   

    

     

    
    

     

       W[num++] = i*w ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

          可以先看下这个博客 ，看几次后你就会理解它的思想了。这里再说一下我的理解。

当你在拿一件物品的时候，如果你细心推一下你会发现只有 j % v  余数相同的时候是有关联的，余数如果不相同是相互独立的( j 指当前要计算的体积，v 指当前物品的体积) 。

这里假设余数为 1 的情况，num = 2 ,体积为 v ,价值为 w .C (总体积)  = 8* v 

 dp  的时候只有这些情况

    dp( 1 )  , dp( v  +  1 )  , dp( 2 * v + 1 )  ,  dp( 3 * v + 1 )  , dp( 4 * v  + 1 )  , dp( 5 * v  + 1 )  ,  dp( 6 * v + 1 )  ,  dp( 7 * v  + 1 ) 

那么 : dp( 2 * v + 1 )  = max { dp( 2 * v + 1 )   , dp( v + 1 )  + w , dp( 1 )  +  2 * w  }

            dp(3 * v + 1)  = max { dp( 3 * v  + 1 )  , dp( 2 * v + 1 )  + w , dp( v + 1)  + 2 * w } 

           dp(4 * v + 1)  = max { dp ( 4 * v + 1 ) , dp( 3 * v + 1 )  + w ,dp( 2 * v + 1) + 2 * w }

           dp(5 * v + 1)  = max { dp( 5 * v + 1 )  , dp( 4 * v + 1 )  +  w , dp( 3 * v + 1 )  + 2 * w }

           dp(6* v + 1)  = max { dp( 6 * v + 1 )  , dp( 5 * v + 1 )  + w , dp( 4 * v + 1 )  + 2 * w }

            dp(7 * v + 1)  = max { dp( 7 * v + 1)  , dp( 6 * v + 1)  + w  , dp( 5 * v + 1) + 2 * w }

每项都是有后面两项递推而来，这样还看不出什么规律的话让我们再变化一下：

让第一行减  2 * w  , 让第二行减 3 * v ,让第三行减 4 * v ……

得到：

            dp( 2  * v + 1 )  = max { dp( 2 * v  + 1 )  - 2 *  w , dp( v  + 1 )  -  w  , dp( 1 )  }  + 2  *  w  ;

            dp(3 * v + 1) = max {  dp ( 3 * v + 1 ) - 3 * w , dp ( 2 * v + 1 )  -  2 * w  , dp( v + 1 ) -   w }  + 3 * w  ;

           dp(4 * v + 1) = max { dp ( 4 * v + 1) - 4 * w , dp(3 * v + 1 )  - 3 * w  , dp( 2 * v + 1)  -  2 * w }  + 4 * w  ;

           dp(5 * v + 1)  = max { dp( 5 * v + 1 )  -  5 * w , dp( 4 * v + 1 )  -  4 * w , dp( 3 * v + 1 )  - 3 * w } + 5 * w ;

           dp(6* v + 1)  = max { dp( 6 * v + 1 )  - 6 * w , dp( 5 * v + 1 )  - 5 * w , dp( 4 * v + 1)  - 4  * w }  + 6  * w  ;

            dp(7 * v + 1)  = max{ dp( 7 * v + 1 )  - 7 * w , dp( 6 * v + 1)  - 6 * w , dp( 5 * v  + 1)  - 5 * w }  + 7 * w  ;

这样变化后明显看出有许多重复的，这样我们可以他们放在一个队列里，然后 每个数只进队列一次。

这样剩下的就是怎样维护队列了：

( 1 ) 删除小于等于当前入队的元素的值。

( 2 ) 删除无效元素，因为如果物品的件数只有 3 件物品，那么，滑动窗口里就只能放 3 个元素，多了的就是无效的元素。

代码~~>

还有一种特殊情况：当 V = W 的时候，只要判断队列中是否有装满的情况就可以了，因为如果某个体积成立，它加上在 k * v 都是可以装满的。这样只要判断当前队列中是否有装满的就可以了。

代码~~>

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/40977543