背包问题基础模型全解

淩亂°似流年 2024-03-23 23:47 8阅读 0赞

## 01背包 ##

状态表示：二维

集合：只从前 i 个物品里面选择总体积 ≤j 选法的集合

属性：选法价值的最大值

状态计算分为 放 i 和 不放 i （要不要把当前物品放进背包）:

*  不放 i 意味着在前 i−1 个物品里面选，且总体积不超过 j
 *  放 i 的话先来看看里面应该都是些什么东西

![8665f4b1acc7a533a9d06fbc0b438334.png][]

如图所示，f\[i\]\[j\] 表示的是 0 至 i 里面所有选法的权值和的最大值，我们可以将 f\[i\]\[j\] 拆成两部分来看待，即 f\[i−1\]\[j−v\[i\]\] 和 i

那么这两段的权值和为 f\[i−1\]\[j−v\[i\]\]+w\[i\] ，由于求最大值，所以我们要比较一下那种选择可以使权值最大，于是我们就得到了状态转移方程

f\[i\]\[j\]=max(f\[i−1\]\[j\],f\[i−1\]\[j−v\[i\]\]+w\[i\])

由于下标不能是负数，所以上述转移方程要求 j≥w\[i\] 。当 j<w\[i\] 时，f\[i\]\[j\]=f\[i−1\]\[j\]

综上所述，可以得出：

f\[i\]\[j\]=\{(1)f\[i−1\]\[j\],j<w\[i\](2)max(f\[i−1\]\[j\],f\[i−1\]\[j−v\[i\]\]+w\[i\]),j≥w\[i\]

#include <iostream>
    using namespace std;
    const int N = 1010;
    int f[N][N],v[N],w[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                f[i][j]=f[i-1][j];
                if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
        cout<<f[n][m];
        return 0;
    }

注意题目给的数据，我们的数组的第二维是跟着容量的范围而不是物品数的范围

优化版本：  
我们可以发现在 f\[i\]\[j\] 的时候只用到了 f\[i−1\]\[j\] ，这样 f\[i−2\]\[j\]，f\[i−3\]\[j\] …… 就被浪费掉了，而且，我们二维的状态只用到了j 和 j−wi 都是 ≤j 不会在两侧，于是我们就可以用滚动数组来优化这个问题

首先，我们直接删除掉 i 这个状态，那么原方程就会变成：

f\[j\]=\{(3)f\[j\],j<w\[i\](4)max(f\[j\],f\[j−v\[i\]\]+w\[i\]),j≥w\[i\]

由于 f\[j\]=f\[j\] 是恒等式，直接删去，由于 max(f\[j\],f\[j−v\[i\]\]+w\[i\]) 要求 j≥w\[i\] ，所以 j 直接从 w\[i\] 开始枚举

好，接下来再看变形后的式子与原来的方程是否是等价的，答案是否定的

由于我们的 j 是从小到大枚举的，所以 j−v\[i\] 会在 j 之前被算，相当于二维的 f\[i\]\[j−v\[i\]\] 与原来的方程不符，那么如何解决这个问题呢？ 我们可以让 j 从大到小枚举，这样就保证了当我们计算 f\[j\] 的时候 f\[j−v\[i\]\] 因为比 j 小，所以还没有被更新，用的就是 i−1 层的 f\[j−v\[i\]\] ，问题解决

01背包如何保证拿一次？ 那么当前背包的体积就要去找前面的，而前面的都肯定是没有拿过这个物品的，所以可以保证只拿一次。

当然我们可以边输入边计算，又可以省下数组的空间

#include <iostream>
    using namespace std;
    const int N = 1010;
    int f[N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int v,w;
            cin>>v>>w;
            for(int j=m;j>=v;j--)
                f[j]=max(f[j],f[j-v]+w);
        }
        cout<<f[m];
        return 0;
    }

## 完全背包 ##

> [Acwing 3 完全背包问题][Acwing 3]

状态表示：二维

集合：所有只考虑前 i 个物品，且总体积 ≤j 选法的集合

属性：选法价值的最大值

状态计算以第 i 个物品选几个为划分，注意体积不能超过 j ，即 k×v\[i\]≤j

注意当 k=0 时就相当于不选，所以需要从 0 开始枚举，这里还需要对 f\[i\]\[j\] 打擂台，有别于01背包

我们可以得出状态转移方程

f\[i\]\[j\]=max(f\[i\]\[j\],f\[i−1\]\[j−k×v\[i\]\]+w\[i\])

#include <iostream>
    using namespace std;
    const int N = 1010;
    int f[N][N],v[N],w[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k*v[i]<=j;k++)
                    f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
        cout<<f[n][m];
        return 0;
    }

那么这样的时间复杂度大概是 O(m2n) 的，显然不行

我们来想想如何优化

首先，将原方程展开得：

f\[i\]\[j\]=max(f\[i−1\]\[j\],f\[i−1\]\[j−v\[i\]\]+w\[i\],f\[i−1\]\[j−2×v\[i\]\]+2×w\[i\],...)

然后再与 f\[i\]\[j−v\[i\]\] 做一下对比：

f\[i\]\[j−v\[i\]\]=max(f\[i−1\]\[j−v\[i\]\],f\[i−1\]\[j−2×v\[i\]\]+w\[i\],...)

那么我们可以发现，f\[i\]\[j\] 仅仅比 f\[i\]\[j−v\[i\]\] 多了一个 f\[i−1\]\[j\] ，然后后面的每一项都多一个 w\[i\]

于是我们就可以将 f\[i\]\[j−v\[i\]\] 加上 w\[i\] 转化成 f\[i−1\]\[j−v\[i\]\]+w\[i\],f\[i−1\]\[j−2×v\[i\]\]+2×w\[i\],...

再与 f\[i−1\]\[j\] 比较一下最大值就行了

于是我们就得到了优化后的状态转移方程

f\[i\]\[j\]=\{(5)f\[i−1\]\[j\],j<w\[i\](6)max(f\[i−1\]\[j\],f\[i\]\[j−v\[i\]\]+w\[i\]),j≥w\[i\]

#include <iostream>
    using namespace std;
    const int N = 1010;
    int f[N][N],v[N],w[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
            {
                if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
                else f[i][j]=f[i-1][j];
            }
                
        cout<<f[n][m];
        return 0;
    }

我们可以发现，这个方程跟01背包非常像，所以我们可以按照01背包的思路优化成1维

注意完全背包跟01背包唯一的区别就在于01背包是 f\[i−1\]\[j−v\[i\]\]+w\[i\] 而完全背包是 f\[i\]\[j−v\[i\]\]+w\[i\]

完全背包没有 -1 这个问题，所以从小到大遍历，从大到小是不行的，从大到小会使得每个物品就拿一次（参见01背包的优化）

从大到小的话会导致 f\[j\] 在 f\[j−v\[i\]\] 之前算，导致算 f\[j\] 的时候用的 f\[j−v\[i\] 的值是 i−1 层的，变成01背包了

#include <iostream>
    using namespace std;
    const int N = 1010;
    int f[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int v,w;
            cin>>v>>w;
            for(int j=v;j<=m;j++)
                f[j]=max(f[j],f[j-v]+w);
        }
        cout<<f[m];
        return 0;
    }

## 多重背包 ##

> [Acwing 4 多重背包问题I][Acwing 4 _I]

状态表示：二维

集合：所有只从前 i 个物品中选，并且总体积 ≤j 选法的集合

属性：每一个选法对应的总价值的最大值

状态计算和完全背包非常像，不过将 k 枚举结束的条件改成 s 个

不过这样的时间复杂度很高，O(m2n)

#include <iostream>
    using namespace std;
    const int N = 105;
    int f[N][N];
    int v[N],w[N],s[N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                    f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
        cout<<f[n][m];
        return 0;
    }

然后我们尝试优化，既然和完全背包很像，我们先来试试通过完全背包的方式优化

首先将原方程展开得：

f\[i\]\[j\]=max(f\[i−1\]\[j\],f\[i−1\]\[j−v\[i\]\]+w\[i\],f\[i−1\]\[j−2×v\[i\]\]+2×w\[i\],...,f\[i−1\]\[j−s\[i\]×v\[i\]\]+s\[i\]×w\[i\])

再对比 f\[i\]\[j−v\[i\]\] ：

f\[i\]\[j−v\[i\]\]=max(f\[i−1\]\[j−v\[i\]\],f\[i−1\]\[j−2×v\[i\]\]+w\[i\],...,f\[i−1\]\[j−s\[i\]×v\[i\]\]+(s\[i\]−1)w\[i\],f\[i−1\]\[j−(s\[i\]+1)w\[i\]\]+s\[i\]×w\[i\])

我们发现两个式子很像，不过，f\[i\]\[j−v\[i\]\] 多了一项 f\[i−1\]\[j−(s\[i\]+1)w\[i\]\]+s\[i\]×w\[i\]) ，我们不可以通过前 n 个数的最大值和最后一个数，求出前 n−1 个数的最大值，所以这样的方法是不可行的

我们可以用二进制的方式来优化  
例如当 s=1023 时，我们真的需要从 0 枚举到 1023 吗？  
我们可以将若干个 i 个物品打包，比如说我们可以打包成10组：1,2,4,8,...512  
每组最多选一次，我们可以用这10组凑出来 0 到 1023 的任何数（二进制可以表示出所有的十进制整数）

那么对于任何一个 s，我们将物品打包成 20,21,22,...,2k，20 一直加到 2k≤s  
如果 20 一直加到 2k<s，再补上一个 c  
那么显然有 c<2k+1  
那么来证明一下是不是这样就能表示出 0 到 s 的所有数？  
首先，20 一直加到 2k 能凑出 0 到 2k+1−1 的所有数（等比数列公式）  
补上 c 以后便能凑出 0 到 2k+1+c 的所有数，2k+1+c 即 s  
所以是可行的，我们将原本的 O(m2n) 优化到了 O(m2logn)  
转化完之后再求一遍01背包就行了  
注意我们的打包时数组体积的部分要开 log22000×1000 log22000 要上取整得 12

#include <iostream>
    using namespace std;
    const int N = 25000;
    int n,m;
    int v[N],w[N],f[N];
    int main()
    {
        cin>>n>>m;
        int cnt=0; //重新打包后物品的个数
        for(int i=1;i<=n;i++)
        {
            int a,b,s;
            cin>>a>>b>>s;
            int k=1; //2的k次幂
            while(k<=s)
            {
                cnt++;
                v[cnt]=a*k;
                w[cnt]=b*k;
                s-=k;
                k*=2;
            }
            //补上的c
            if(s>0)
            {
                cnt++;
                v[cnt]=a*s;
                w[cnt]=b*s;
            }
        }
        n=cnt;
        for(int i=1;i<=n;i++)
            for(int j=m;j>=v[i];j--)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
        cout<<f[m];
        return 0;
    }

其实还有单调队列的优化方式，不过是提高的内容，等我之后滚回来更新

## 分组背包 ##

> [Acwing 9 分组背包问题][Acwing 9]

状态表示：二维  
集合：只从前 i 个物品里面选，且总体积 ≤j 的所有选法  
属性：选法价值的最大值

状态计算：枚举第 i 组，物品选第几个或不选  
不选也就是 f\[i−1\]\[j\]  
选第 k 个也就是 f\[i−1\]\[j−v\[i\]\[k\]\]+w\[i\]\[k\]  
注意 k 枚举的是下标，所以从0开始

#include <iostream>
    using namespace std;
    const int N = 105;
    int f[N][N],v[N][N],w[N][N],s[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) 
        {
            cin>>s[i];
            for(int j=0;j<s[i];j++) cin>>v[i][j]>>w[i][j];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                f[i][j]=f[i-1][j];
                for(int k=0;k<s[i];k++)
                {
                    if(v[i][k]<=j) 
                        f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
                }
            }  
        }
        cout<<f[n][m];
        return 0;
    }

直接删去一维，得到状态转移方程

f\[j\]=max(f\[j\],f\[j−v\[i\]\[k\]\]+w\[i\]\[k\]),1≤k≤s\[i\]

#include <iostream>
    using namespace std;
    const int N = 105;
    int f[N],s[N],v[N][N],w[N][N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            for(int j=0;j<s[i];j++) cin>>v[i][j]>>w[i][j];
        }
        for(int i=1;i<=n;i++)
            for(int j=m;j>=0;j--)
                for(int k=0;k<s[i];k++)
                    if(v[i][k]<=j)
                        f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        cout<<f[m];
        return 0;
    }

## 混合背包 ##

> [Acwing 7 混合背包问题][Acwing 7]

此为几种背包的模型（01背包、多重背包、完全背包）的综合使用，所以如果弄懂了前几种背包模型，混合背包的问题也会迎刃而解，这里主要介绍一种写法使得代码可读性变高  
首先我们知道多重背包实际上是转化为01背包来做的，所以我们如果遇到多重背包时，我们直接将它加进去，最后当作01背包解决就行了  
在代码中，我使用了结构体，一个是物品的种类，另外两个是体积和权值  
输入多重背包的时候，直接二进制优化好再加进 vector 就行了  
最后根据物品类型的不同分别处理就行了

#include <iostream>
    #include <vector>
    using namespace std;
    const int N = 1010;
    int f[N];
    struct Thing
    {
        int kind,v,w;
    };
    vector<Thing> things;
    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int v,w,s;
            cin>>v>>w>>s;
            if(s==-1) things.push_back({0,v,w});
            else if(s==0) things.push_back({1,v,w});
            else
            {
                int k=1; 
                while(k<=s)
                {
                    things.push_back({0,v*k,w*k});
                    s-=k;
                    k*=2;
                }
                if(s>0) things.push_back({0,v*s,w*s});
            }
        }
        for(auto thing:things)
        {
            if(thing.kind==0)
            {
                for(int j=m;j>=thing.v;j--) 
                {
                    f[j]=max(f[j],f[j-thing.v]+thing.w);
                }
            }
            else
            {
                for(int j=thing.v;j<=m;j++) 
                {
                    f[j]=max(f[j],f[j-thing.v]+thing.w);
                }
            }
        }
        cout<<f[m];
        return 0;
    }

[8665f4b1acc7a533a9d06fbc0b438334.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/4eacc25436aa428db4d1222a174f8282.png
[Acwing 3]: https://www.acwing.com/problem/content/3/
[Acwing 4 _I]: https://www.acwing.com/problem/content/4/
[Acwing 9]: https://www.acwing.com/problem/content/9/
[Acwing 7]: https://www.acwing.com/problem/content/7/