[DP之多重背包优化方法]

首先我们看一道有趣的题目

然后这道题很快想到是一个多重背包和无限背包混合体

那么我们就以这道题来讨论一下多重背包的优化

首先我们看看朴素打法

memset(F,63,sizeof(F)); F[0]=0;
  for(int i=1;i<=N;i++)
     for(int k=0;k<=C[i];k++)
       for(int j=T*2;j>=0;j--)
          if(j-V[i]>=0) F[j]=min(F[j],F[j-V[i]]+1);

很简单很好懂但是这样做导致时间复杂度为O(N*C*T) 这道题来看超时到爆炸

那么我们考虑两种方法第一种是像wph写的首先贪心一会儿然后再背包答案大概在T到2*T的范围内

但是这种方法导致代码很玄学因为贪心的时候很有可能有一些东西处理不到

那么我们考虑第二种方法就是优化多重背包因为无限背包的时间是足够的

优化多重背包有两种算法，但是下面只介绍最快的：

1.用二进制优化这个好像我有写过但不知道怎么打和原理了陈年老事具体可以问wph 时间复杂度O(NTlog(C))

2.可以用单调队列进行优化时间复杂度为O(NT)

我只讨论单调队列优化我们先列出有

F[i][j]=min(F[i-1][j-vi*k]+k) (0<=k<=ci)

那么我们发现每一次都是和vi有关的我们其实可以把式子变一下

令a=j/v[i] b=j%v[i] j=a*v[i]+b

F[j]=min(F[b+k*v[i]]-k)+a (a-c[i]<=k<=a)

我们把k枚举就是单调队列了，具体看下面

其实我们在做j这个状态的时候 k和a是相同的当然方便理解因为以前的是k 现在的是a 只是对于当前来说我的a和k是一样但是对于别的来说我就要找最小的k

我们可以枚举b 然后可以每次都 +v[i] 处理这样的话每一次每个位置只会被扫1遍大大减少了时间所以时间复杂度为O(NT)很显然

memset(F,63,sizeof(F)); F[0]=0;
  for(int i=1;i<=N;i++)
  {
    for(int j=0;j<=50000;j++) G[j]=F[j];
    
    for(int b=0;b<V[i];b++)
    {
      head=1; tail=0;
      for(int j=b;j<=50000;j+=V[i])
      {
        int a=j/V[i];
        while(head<=tail&&Q[head].first<a-C[i]) head++;
        if(head<=tail) F[j]=min(G[j],Q[head].second+a);
        while(head<=tail&&Q[tail].second>=G[j]-a) tail--;
        Q[++tail]=make_pair(a,G[j]-a);
        
      }
    }
  }

良心的贴一道这道例题的链接这里