单调队列优化多重背包

原题链接

• 朴素多重背包问题：

当外层循环到i时，dp[j]表示从前i种物品中选出若干个放入背包，体积之和为j时，价值之和最大值是多少

for (int i = 1; i <= n; ++ i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j <= m; ++ j) 
            for (int k = 0; k <= s && k * v <= j; ++ k) 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v] + k * w);
    }

理论：1 ~ N分为X类，每一类都是余数为1 ~ X的集合，那么这X类的并集还是1~N

• 优化成一维滚动数组：

dp[m] 表示容量为m的情况下，获得的最大价值，逆序循环m，在状态转移时，考虑选取第i个物品的个数k，针对每一类物品 i ，我们都更新一下 dp[m] .....dp[0] 的值，最后 dp[m] 就是一个全局最优值

dp[m] = max(dp[m], dp[m-v] + w, dp[m-2*v] + 2*w, dp[m-3*v] + 3*w, ...)

• 单调队列优化

接下来，我们把 dp[0] ......dp[m] 写成下面这种形式:

dp[0] , dp[v] , dp[2v], dp[3v], ... , dp[kv]

dp[1], dp[v+1], dp[2v+1], dp[3v+1], ... , dp[kv+1]

dp[2], dp[v+2], dp[2v+2], dp[3v+2], ... , dp[kv+2]

...

dp[j-1], dp[v+j-1], dp[2v+j-1], dp[3v+j-1], ... , dp[kv+j-1]

其中 0 < = （ j - 1 ） < v ，m = k * v + j - 1

所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的，

对于max{ dp[j-1], dp[v+j-1], dp[2v+j-1], dp[3v+j-1], ... , dp[kv+j-1] },可以通过一个单调队列来维护

把状态j按照除以Vi的余数分组，每一组分别进行计算，余0组，余1组....余Vi-1组，就是j个单调队列

以dp[j]为例，在维护一个单调队列中，当更新dp数组时

dp[j]=max(dp[j])
dp[j+v]=max(dp[j]+w,dp[j+v])
dp[j+2v]=max(dp[j]+2*w,dp[j+v]+w,dp[j+2v])
.....
发现这个队列中前面的数，每次都会增加一个 w ，所以需要做一些转换

dp[j]=max(dp[j])
dp[j+v]=max(dp[j],dp[j+v]-w)+w
dp[j+2v]=max(dp[j],dp[j+v]-w,dp[j+2v]-2w)+2w
.....
取max中的通项，每次入队时的值是 dp[j+kv] - kw，当前dp值减去k个w

• 维护单调队列

1）维护队列元素的个数，如果不能继续入队，弹出队头元素
2）分别考虑放和不放第i个物品（省去一维），择优

dp[i][k] = dp[i - 1][k];  // 不放物品i
if (hh <= tt) 
    dp[i][k] = max(dp[i][k], dp[i - 1][q[hh]] + (k - q[hh]) / v * w);  // 放物品i

3）维护队列的单调递减，最大值放在队列头，降低到一维的时候，我们要用i-1时刻去更新，而顺序枚举时会导致旧的值被覆盖，所以每次更新最大值需要备份数组pre更新dp，因为dp[k]通过前面的pre[q[hh]]来更新最大值，窗口在pre数组上滑动，因此
dp[k]=窗口中的最大值+还能放入物品的价值

4）每次换另一种物品时用dp数组更新pre数组，因此迭代出的dp[m]就是最大值

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=20010;

int n,v;
int dp[N],q[N],g[N];

int main()
{
    cin>>n>>v;
    for(int i=0;i<n;i++)
    {
        int c,w,s;
        cin>>c>>w>>s;//体积、价值和数量
        memcpy(pre,dp,sizeof dp);//pre表示i-1时刻，dp数组为i时刻
        for(int j=0;j<c;j++)//枚举余数，j个单调队列
        {
            int hh=0,tt=-1;//建立单调队列
            for(int k=j;k<=v;k+=c)//枚举候选集合
            {
                if(hh<=tt&&k-q[hh]>s*c) hh++;//队列满了
                if(hh<=tt) dp[k]=max(dp[k],pre[q[hh]]+(k-q[hh])/c*w);
//最大值在队列头部，pre[q[hh]]记载，加上还能放入物品的价值，取决策，放还是不放，更新dp数组的最大值
                while(hh<=tt&&pre[q[tt]]-(q[tt]-j)/c*w<=pre[k]-(k-j)/c*w) tt--;
//维护单调队列递减，新加入的元素满足上面推导的通项公式
                q[++tt]=k;//插入队列
            }
        }
    }
    cout<<dp[v]<<endl;
    return 0;
}