最新要闻

广告

手机

2016年金球奖排名：C罗第4次获奖，梅西、格列兹曼二三位

2016年金球奖排名：C罗第4次获奖，梅西、格列兹曼二三位

 幸亏过路女司机凌晨多看了两眼 网友：疲劳驾驶很危险

幸亏过路女司机凌晨多看了两眼 网友：疲劳驾驶很危险

家电

  1. 首页
  2. 移动通信
  3. 内容

背包问题基础模型全解

来源：博客园

01背包

Acwing 2. 01背包问题

状态表示：二维


(相关资料图)

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

属性：选法价值的最大值

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

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

如图所示，\(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\geq w[i]\) 。当 \(j

综上所述，可以得出：

\[f[i][j]=\left\{\begin{align}&f[i-1][j],&j#include 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[i][j]\) 的时候只用到了 \(f[i-1][j]\) ，这样 \(f[i-2][j]\)，\(f[i-3][j]\) …… 就被浪费掉了，而且，我们二维的状态只用到了\(j\) 和 \(j-w_i\) 都是 \(\leq j\) 不会在两侧，于是我们就可以用滚动数组来优化这个问题

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

\[f[j]=\left\{\begin{align}&f[j],&j由于 \(f[j]=f[j]\) 是恒等式，直接删去，由于 \(max(f[j],f[j-v[i]]+w[i])\) 要求 \(j\geq 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 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<

完全背包

Acwing 3 完全背包问题

状态表示：二维

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

属性：选法价值的最大值

状态计算以第 \(i\) 个物品选几个为划分，注意体积不能超过 \(j\) ，即 \(k×v[i]\leq 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 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<

那么这样的时间复杂度大概是 \(O(m^2n)\) 的，显然不行

我们来想想如何优化

首先，将原方程展开得：

\[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]=\left\{\begin{align}&f[i-1][j],&j#include 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<

我们可以发现，这个方程跟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 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<

多重背包

Acwing 4 多重背包问题I

状态表示：二维

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

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

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

不过这样的时间复杂度很高，\(O(m^2n)\)

#include 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[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\)，我们将物品打包成 \(2^0,2^1,2^2,...,2^k\)，\(2^0\) 一直加到 \(2^k \leq s\)如果 \(2^0\) 一直加到 \(2^k < s\)，再补上一个 \(c\)那么显然有 \(c<2^{k+1}\)那么来证明一下是不是这样就能表示出 \(0\) 到 \(s\) 的所有数？首先，\(2^0\) 一直加到 \(2^k\) 能凑出 \(0\) 到 \(2^{k+1}-1\) 的所有数（等比数列公式）补上 \(c\) 以后便能凑出 \(0\) 到 \(2^{k+1}+c\) 的所有数，\(2^{k+1}+c\) 即 \(s\)所以是可行的，我们将原本的 \(O(m^2 n)\) 优化到了 \(O(m^2 logn)\)转化完之后再求一遍01背包就行了注意我们的打包时数组体积的部分要开 \(log_2 2000×1000\) \(log_22000\) 要上取整得 \(12\)

#include 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<

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

分组背包

Acwing 9 分组背包问题

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

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

#include 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>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

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

\[f[j]=max(f[j],f[j-v[i][k]]+w[i][k]),1\leq k\leq s[i]\]
#include 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>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

混合背包

Acwing 7 混合背包问题

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

#include #include using namespace std;const int N = 1010;int f[N];struct Thing{    int kind,v,w;};vector 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<

关键词：