単調キュー最適化マルチバックパック(構造の問題を含む)

1.前言:注:本稿では、v[i]で物体の価値を表し、w[i]で物体の代価を表し、c[i]で物体の数の上限を表す.
多重リュック問題は動的計画の基礎内容であるべきであるが,まず多重リュックの公式を振り返ると,dp[i][j]はi番目の物品を選択し,総代価がjの場合に得られる最大価値の総和を表す.
では、dp[i][j]=max(dp[i-1][j-k*w[i]+k*v[i]);(0<=k<=c[i])スクロール最適化後、dp[j]=(dp[j-k*w[i]+k*v[i]);( j : maxn – > w[i] )
明らかに,i,j,kの3次元を列挙し,時間複雑度はO(n^3)である.このような時間の複雑さは,問題に必要なものを満たすことができない場合が多い.解決策は2つあります.バイナリ最適化と単調キュー最適化です.今日はここで,時間的複雑さをO(n^2)に低減できる単調キューの最適化を見てみよう.
2.式の推論:
多重リュック問題の式を変形してみましょう
dp[ i ][ j ] = max( dp[ i-1 ][ j - k*w[i] ] + k*v[i] );
我々はj=a*w[i]+bを原式に代入する:dp[i][a*w[i]+b]=max(dp[i-1][a*w[i]+b-k*w[i]+k*v[i]);
同類項:dp[i][a*w[i]+b]=max(dp[i-1][(a-k)*w[i]+b]+k*v[i]);
分離定数:dp[i][a*w[i]+b]=max(dp[i-1][(a-k)*w[i]+b])+k*v[i];
最も重要な一歩:a-k=tを!だからk=a-t
代入原式中:dp[i][a*w[i]+b]=max(dp[i-1][t*w[i]+b])+(a-t)*v[i];分解:dp[i][a*w[i]+b]=max(dp[i-1][t*w[i]+b])+a*v[i]-t*v[i];
項を移動して、最終式を得る:dp[i][a*w[i]+b]-a*v[i]=max(dp[i-1][t*w[i]+b]-t*v[i]);
3.優先キューの実現:得られた式:dp[i][a*w[i]+b]-a*v[i]=max(dp[i-1][t*w[i]+b]-t*v[i]);左右の式を観察すると、不思議なことに、左右の式は等しい!!!まずコードを貼り付けます.

for(i = 1; i <= N ; i ++)
  {
      for(b = 0 ; b <= w[i]-1 ; b ++)
      {
         hd = 1; tl = 0;
         for(a = 0 ; a*w[i]+y <= M ;a ++)
         {
            int now = dp[i-1][a*w[i]+b]-a*v[i];
            while( (a-lk[hd])>c[i] && hd<=tl)hd++;
            while( (dp[i-1][lk[tl]*a[i]+b]-lk[tl]*v[i])<=now && hd<=tl)tl--;
            lk[++tl] = k;
            dp[i][a*w[i]+b] = dp[i-1][lk[hd]*w[i]+b]-lk[hd]*v[i]+a*v[i];
          }
       }
   }

私たちは一歩一歩(j=a*w[i]+b):for(i = 1; i <= N ; i ++)//列挙物体for(b = 0 ; b <= w[i]-1 ; b ++)//余剰クラス(すなわち余剰)を列挙するfor(a = 0 ; a*w[i]+y <= M ;a ++)//列挙件数(すなわちaの値)while( (a-lk[hd])>c[i] && hd<=tl)hd++; ----------------------------------------“￥”//先頭からの移行に必要な件数が件数上限より大きい場合は、先頭要素をポップアップ
重要なステップ:while( (dp[i-1][lk[tl]*a[i]+b]-lk[tl]*v[i])<=now && hd<=tl)tl--;//キューの末尾要素の対応値が現在の対応値よりも小さい場合は、キューの末尾要素がポップアップされます.つまり、キューの末尾要素が現在の要素の対応値よりも大きいまでポップアップされます.
//この操作はなぜか説明する必要がある.//私たちが順番に追加するため、前の要素は一定の件数が少なく、点数が足りない現象が発生しやすい(上「￥」操作を参照).//価値が低く、先に淘汰されると、この要素は意味がなく、ポップアップします.dp[i][a*w[i]+b] = dp[i-1][lk[hd]*w[i]+b]-lk[hd]*v[i]+a*v[i]; //dp[ i ][ a*w[i]+b ] - a*v[i] = max( dp[ i-1 ][ t*w[i]+b ] - t*v[i]) ; //我々の初期式シフト項はdp[i][a*w[i]+b]を計算する.
4.多重バックパックの変形:簡単に言えば、n個の物体を構築できるかどうか、総代価がJ以下の場合、価値の総和が1~Kのうちどれだけの値を構築できるかを尋ねる.タイトルはPOJ 1742 coin転送ゲートです.http://poj.org/problem?id=1742この問題は実は前の問題に比べてかえって簡単になった.転送可能な要素を格納するキューを構築します.数が足りなければ、チームは初めてチームを出ます.これではキューに要素があれば、転送できることを示します.コード:

#include
#include
#include
#include
#include
#include
using namespace std;

inline int gi()
{
    int date = 0 , m = 1; char ch = 0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch = getchar();
    if(ch == '-'){m = -1; ch = getchar();}
    while(ch<='9' && ch>='0'){
        date = date * 10 + ch - '0';
        ch = getchar();
    }return date * m;
} 

//     ：
//              ，       
//         O（n^2）      
//           （01    、    ）     。

bool dp[100005];
int ans,n,m;
int lk[100005];
int a[150],c[150];

void solve_coin()
{
    for(int i = 1; i <= m ; i ++)dp[i] = 0;
    dp[0] = true; ans = 0;
    for(int i = 1; i <= n ; i ++)
    {
        if(c[i] == 1){                                 //    ：01      
            for(int s = m ; s >= a[i]; s -- )
             if(!dp[s] && dp[s - a[i]])dp[s] = true;
        } 
        else if(a[i]*c[i]>=m){                         //           ，  
            for(int s = a[i]; s <= m ; s ++)
             if(!dp[s] && dp[s - a[i]])dp[s] = true;
        }

        //        ：
        else for(int gg = 0 ; gg <= a[i] - 1; gg ++) //    
        {
            int hd = 1,tl = 0;
            for(int s = 0; s*a[i] + gg <= m ; s ++)
            {
                while(hd<=tl && s - lk[hd]>c[i])hd++;            //         
                if(dp[s*a[i]+gg])lk[++tl]=s;                     //  
                else if(hd<=tl)dp[s*a[i]+gg] = true;             //  
            }
        } 
    }
    return;
}

int main()
{
    freopen("coin.in","r",stdin);
    while(1)
    {
        n = gi(); m = gi();           //n   ，  1~m
        if(n==0 && m==0)break;
        for(int i = 1; i <= n ; i ++)a[i] = gi();   //         
        for(int i = 1; i <= n ; i ++)c[i] = gi();   //           
        solve_coin();
        for(int i = 1; i <= m ; i ++)
         if(dp[i])ans ++;
        printf("%d
",ans);
    }return 0;
}

5.尾言:多重リュックの最適化により、単調な列の効果が見られるはずです.しかし、最后に、私が言いたいのは、単调なキューは时にはDPを最適化することができます!!私自身の経験によると、一般的にこのようにできるDPには2つの特徴があります.1>maxを取るかminを取るか2>私たちの簡略化を通じて、DP式の左右の両側を同じ形式にすることができます.しかし、単調キューによるDPの最適化は、具体的なテーマに基づいて行われるので、ここでは説明しない理由でもあります.みんなが自分でこのような問題型を研究することができることを望んで、最後に、私の少しの見解がみんなに役に立つことができることを望んで、ありがとうございます.