背包DP

01背包

$n$件物品，$m$的背包容积

最最最最最最最最最最最最最最入机的$DP$(没有之一)，但也是后面的$DP$的基础，并且它也会带出一个我们常用的优化方式

最基础的思路，$f[i][j]$代表在前$i$件物品中选了重量不超过$j$的最大价值，边界为$f[0][0]=0$

易得转移方程$f[i][j]=max(f[i][j],f[i-1][j-weight[i]]+value[i])$，我们就能得到一份时间和空间都是$nm$的代码

for( int i=1;i<=n;i++ )//枚举不同的物品
    for( int j=weight[i];j<=m;j++ )//枚举重量
    {
        f[i][j]=f[i-1][j];
        f[i][j]=max(f[i][j],f[i-1][j-weight[i]]+value[i])//DP转移
    }

丹斯，我们发现所有的$f[i]$均由$f[i-1]$转移得到，这一维并没有什么实际上的定位作用，所以我们可以使用滚动数组降维将空间复杂度降到$m$

for( int i=1;i<=n;i++ )//枚举不同的物品
    for( int j=m;j>=weight;j-- )//枚举重量，因为只有一个物品，只能由旧的更新新的，所以使用倒序
        f[j]=max(f[j],f[j-weight[i]]+value[i])//DP转移

---

完全背包

$n$件物品，$m$的背包容积

$01$背包的变体，无论是思路还是代码实现上都和$01$背包区别不大，无非就是所有的物品可以无限选罢了

$f[i][j]$代表在前$i$件物品中选了重量不超过$j$的最大价值，边界为$f[0][0]=0$

易得转移方程$f[i][j]=max(f[i][j],f[i][j-weight[i]]+value[i])$

for( int i=1;i<=n;i++ )//枚举不同的物品
    for( int j=weight[i];j<=m;j++ )//枚举重量
    {
        f[i][j]=f[i-1][j];
        f[i][j]=max(f[i][j],f[i][j-weight[i]]+value[i])//DP转移
    }

再滚动数组优化一下可得

for( int i=1;i<=n;i++ )//枚举不同的物品
    for( int j=weight[i];j<=m;j++ )//枚举重量，因为可以无限选择，能由新的更新新的，所以使用正序
        f[j]=max(f[j],f[j-weight[i]]+value[i])//DP转移

---

多重背包

$n$件物品，$m$的背包容积，第$i$件物品$number[i]$个

首先，最直接的思路就是把它分解成$k \times 01$背包问题来写，写成这样

for( int i=1;i<=n;i++ )//枚举不同的物品
    for( int j=weight[i];j<=m;j++ )//枚举重量
        for( int k=1;k<=number[i] && k*weight[i] <= j;k++ )//枚举个数
            f[i][j]=max(f[i][j],f[i-1][j-k*weight[i]]+k*value[i])//DP转移

优点是一眼顶针没有思维难度，缺点就是太慢了，整整$O(nm \sum_{i=1}^{n} number[i])$直接$T$飞

注意力惊人的你应该一下就能注意到这段代码的主要问题在于枚举个数的时候太耗费时间了

思考一下，在做一些值域情况允许的题目，对于这种选择我们一般会怎么做->二进制拆分

于是把$number[i]$拆分出来，例如$17=[0,1,2,4,8,16]+\{0,1\}$，我们就一定可以组合出$[0,17]$间的任意整数，也就变成了01背包问题

这样时间复杂度就降到了$O((n + \sum_{i=1}^{n} log(number[i])) \times m)$

//读入时分组
for (int i = 1; i <= n; i++)
{
    int v, w, num;
    cin>>v>>w>>num;
    int k = 1;//下一次拆分得到的大小
    while ( k <= num )//二进制拆至不能再拆
    {
        cnt++;
        value[cnt]=v*k;
        weight[cnt]=w*k;
        num-=k;
        k<<=1;
    }
    if( num > 0 )//没有恰好拆分完，需要补上剩余部分保证k+1->k+num可以被组合出来
    {
        cnt++;
        value[cnt]=v*num;
        weight[cnt]=w*num;
    }
}
n=cnt;

//01背包
for( int i=1;i<=n;i++ )//枚举不同的物品
    for( int j=m;j>=weight;j-- )//枚举重量，因为只有一个物品，只能由旧的更新新的，所以使用倒序
        f[j]=max(f[j],f[j-weight[i]]+value[i])//DP转移

它的正确性在于，对于$[0,number[i]]$间的所有数，都可以用拆分出的小子集组合得到，例如$13=1+4+8$得到，于是可以讨论到所有的情况保证正确

再看看不变成$01$背包情况$DP$的转移方程，$f[i][j]=max_{k=0}^{number[i]}(f[i-1][j-k*weight[i]]+k*value[i])$

发现没有，这个决策不是连续的，它是一个断断续续的决策，$f[i-1][j]，f[i-1][j-weight[i]]，f[i-1][j-2*weight[i]]......f[i-1][j-number[i]*weight[i]]$

但这些决策点是同行等差列的，第一维都是$i-1$，每两个决策点隔着一个weight[i]，这就很好了

注意力惊人的你又会发现，如果我们按照背包体积$m$模$weight[i]$分类，余数相同的肯定是一类的

那样我们就可以把这一段当成连续的决策去做，因为实际上枚举余数$p$和当前周期编号$k$，因为$k$是连续的，那么$p+k*weight[i]$实际上就是当前的决策点，这样我们构造出了若干段连续的决策

因为每一个点会扫一次$O(n)$，然后枚举同时枚举余数$p$和$k$，又因为$p \times k \leq m$，所以第二层循环的$\sum$不会超过$m$

又根据单调队列每个元素一进一出的规则，$O(nm)$的时间复杂度已然确定

for( int i=1;i<=n;i++ )//枚举物品
	for( int j=0;j<weight[i];j++ )//枚举余数
    {
        deque< int > dq;//单调队列
        for( int k=0;k*weight[i]+j<=m;k++ )//枚举周期编号
        {
            while( !dq.empty() && dq.front() < k-number[i] ) dq.pop_front();//弹出不在范围内的元素
            while( !dq.empty() && f[i&1^1][dq.back()*weight[i]+j]-dq.back()*value[i] < f[i&1^1][k*weight[i]+j]-k*value[i] ) dq.pop_back();//保证单调性，当前答案更优就弹出队尾
            dq.push_back( k );//放入单调队列
            f[i&1][k*weight[i]+j]=f[i&1^1][dq.front()*weight[i]+j]-dq.front()*value[i]+k*value[i];//更新答案
        }
    }

题外话，其实完全背包也可以使用单调队列来写，各位读者可以试着思考一下如何实现才不是我懒得写了

---

分组背包

$t$组物品，$m$的背包容积，第$i$组物品存放在$vector< int > group[i]$中

经典蒟蒻都会的转成$01$背包时间空间双$O(tm\sum_{i=1}^{t} siz[i])$暴力跑---荣获$MLE$(可能出题人没卡空间，但$O(nm)$的空间确实很差)

for( int i=1;i<=t;i++ )//枚举不同的组
    for( int j=m;j>=1;j-- )//枚举重量
        for( auto k:group[i] )//枚举组内元素，同时转移保证不会出现由同组元素转移得到的答案再次转移的决策
            if( j > weight[k] ) f[i][j]=max(f[i][j],f[i-1][j-weight[k]]+value[k])//DP转移

好了，开始优化吧QAQ

空间优化，因为只能由$i-1$转移到$i$，所以第一维可以滚动省掉，很简单的优化

但是，因为这个分组背包是一个混乱的选择与决策，没有什么规律可言，所以时间复杂度

优化不了！！！

我们也只能得到这个空间优化到$O(n)$的代码

for( int i=1;i<=t;i++ )//枚举不同的组
    for( int j=m;j>=1;j-- )//枚举重量
        for( auto k:group[i] )//枚举组内元素，同时转移保证不会出现由同组元素转移得到的答案再次转移的决策
            if( j > weight[k] ) f[j]=max(f[j],f[j-weight[k]]+value[k])//DP转移

---

依赖背包

也就是带限制的背包问题，这里拿问题选课来举例子

可以发现题目限制了"买$A$必先买$B$"这种条件，我们把这种关系视作$B$是$A$的祖先

这样，将所有关系处理完后，我们就得到了一个森林，我们再使用一个超级原点$0$连接每一颗数的根节点

聪明的你一定发现了，这时任意一个包含超级原点$0$的连通块均满足限制条件

我们就把这个麻烦的问题转化为了一个树上$DP$

这时候，我们的第一反应这个数组的含义怎么定义？大多数人应该会想到$f[p][j]$代表以$p$为根的子树选了$j$个点的最大价值吧(不带根节点$p$)

很棒，请写出转移方程吧！

是不是发现好像不好写了，特别是根节点$p$最烦人，意思是我们想把根节点算进$DP$转移中

于是我们的含义就改为$f[p][j]$代表以$p$为根的所有子树(含点$p$)选了$j$个点的最大价值

//siz是提前预处理的子树大小
void dfs( int p,int fa )
{
    //初始化
    f[p][0]=0, f[p][1]=value[p];
    for( auto to:rode[p] )
    {
        dfs( to,p );
        for( int i=min( q,siz[p] );i;i-- )//枚举是几个点的情况
            for( int j=min( i-1,siz[x] );j>=0;j-- )//枚举在该子树中选几个点
            //01背包逆序枚举
                f[p][i]=max( f[p][i],f[p][i-j]+f[to][j] );//转移，保证要选根节点i>j
    }
}

是不是觉得自己6翻了，这么快解决了这道题目，兴高采烈的交题结果黄了一片，仔细算算时间复杂度--$O(nm^2)$，账号上又多一个$TLE$

没问题啊？怎么绘世呢？

对啊，怎么绘世呢？

看一下第一个$i$的循环，欸！我们明明还没更新后面的子树，但是每次都会搜索到那里，这就很耗费时间了

在前面的循环中，我们扫描到的点可能很少，远远不到整颗子树的大小或者数量限制，但是每次都要跑一遍$min( m,siz[p] )$的循环，虽然有$if$判断，但也是$O(1)$的单次操作

解决方法也很简单，动态更新子树的$siz$，每次只会更新已更新过的点，就会少很多的不必要搜索，这就是分组背包的size优化

这样做的话，当你最开始还没有更新足够的点时，循环只会进行当前更新过的点的数量次，从而跳过大量的非法情况省下时间，秒变$O(nm)$好算法

void dfs( int p,int fa )
{
    //初始化
    f[p][0]=0, f[p][1]=value[p];
    siz[p]=1;
    for( auto to:rode[p] )
    {
        dfs( to,p );
        siz[p]+=siz[to];//当前枚举的子树一共有几个点可以选
        for( int i=min( q,siz[p] );i;i-- )//枚举保留几个点的情况，因为只更新过siz[p]个点，所以最多更新到siz[p]
            for( int j=min( i-1,siz[x] );j>=0;j-- )//枚举在新子树中选几个点
            //01背包逆序枚举
                f[p][i]=max( f[p][i],f[p][i-j]+f[to][j] );//转移，保证要选根节点i>j
    }
}

敲重点：我们要在原限制个数的基础上加一，因为我们要除超级原点外选择$q$个数，而加上超级原点就是$q+1$

---

以上就是$DP$最经典的$5$个模型，其他的部分背包问题大都可以转化为以上问题或利用以上问题提及的方法(滚动数组降维，二进制拆分，单调队列优化，转化为树上问题)进行解决，这里就不多赘述了

在后面，我还会单独出一篇文章讲述$DP$的各种优化方式，to be continue---