背包问题模型

01背包问题

题目链接： https://www.acwing.com/problem/content/2/

状态表示：f[i][j] 表示只从前i个物品中选，且总体积<=j的物品最大价值

集合划分：①不选第i个物品：

​ f[i - 1][j]:表示从1 ---- （i - 1）中个物品选，物品的最大容量为j

​ ②选第i个物品：

​ f[i - 1][j - v[i]] + w[i]:选第i个物品，是上一个物品的最大价值，加上当前物品的最大价值

​ 上一个物品的体积是，选当前物品的总体积，减去当前物品的体积，

​ 即为上一个物品的体积。

​

朴素版本：

#include <iostream>

using namespace std;

const int N = 1010;
int f[N][N],v[N],w[N];
int main()
{
    int n,m;
    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][j],f[i - 1][j - v[i]] + w[i]);
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}

优化版本：

通过对代码做等价变形：

为什么要倒着枚举j呢？

因为j - v[i] 是小于j的，在更新 j 之前j - v[i] 不能被更新，如果从小到大枚举的话，每次枚举的都是第 i 层算出的结果，只有从大到小枚举，每次用到的才是第 i - 1层用到的结果。

#include <iostream>

using namespace std;
const int N = 1010;

int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    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 = m;j >= v[i];j--)
        {
            f[j] = max(f[j],f[j - v[i]] + w[i]);
        }
    }

    cout<<f[m]<<endl;
    return 0;
}

完全背包问题

题目链接： https://www.acwing.com/problem/content/3/

状态表示：f[i][j]表示只从前i个物品中选，且总体积不超过j的所有选法

状态划分：

朴素做法（已超时）：

#include <iostream>

using namespace std;
const int N = 1010;

int f[N][N],v[N],w[N];

int main()
{
    int n,m;
    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;v[i] * k <= j;k++)
            {
                f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + w[i] * k); 
            }
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}

优化做法：

f[i][j] = max(f[i - 1][j],f[i - 1][j - v] + w,f[i - 1][j - 2v] + 2w,f[i - 1][j - 3v] + 3w,……) ①

f[i][j - v] = max( f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w,……) ②

式①从第二项开始，比式②的每一项都大一个w，因此式①从第二项开始的所有项的最大值都对式②的所有项的最大值大一个w

得：f[i][j] = max(f[i - 1][j],f[i][j - v] + w)

#include <iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int 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][j],f[i][j - v[i]] + w[i]);
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}

再优化版本：

通过观察代码我们发现，还可以做到与01背包得类似优化：

与01背包对比：

01背包：f[i][j] = max(f[i - 1][j],f[i - 1][j - v] + w)

完全背包：f[i][j] = max(f[i - 1][j],f[i][j - v] + w)

解释：

01背包中用到的 j - v是i - 1层还未更新的j - v,所以需要从大到小枚举体积（j - v < j）

• 假设枚举到了第二轮：----j,(j - v)----

• 现在是从大到小枚举体积，枚举到j时，然后用到了j - v，由于从大到小枚举，所以j - v还是第一轮的数值，并没有被更新！！！

然而完全背包问题优化版本中，j - v用到的是第i层的j - v,所以不需要从大到小枚举体积（实时更新）

#include <iostream>

using namespace std;

const int N = 1010;

int f[N],v[N],w[N];

int main()
{
    int n,m;
    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 = v[i];j <= m;j++)
        {
            f[j] = max(f[j],f[j - v[i]] + w[i]);
        }
    }

    cout<<f[m]<<endl;
    return 0;
}

多重背包问题Ⅰ

题目链接： https://www.acwing.com/problem/content/4/

状态表示：所有从前i个物品中选，不超过j的物品的价值最大

集合划分：

#include <iostream>

using namespace std;
const int N = 110;

int f[N][N],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] && v[i] * k <= j;k++)
            {
                f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}

多重背包问题Ⅱ

题目链接： https://www.acwing.com/problem/content/5/

首先：

f[i][j] = max(f[i - 1][j],f[i - 1][j - v] + w,f[i - 1][j - 2v] + 2w,……,f[i - 1][j - sv] + sw)

f[i][j - v] = max( f[i - 1][j - v], f[i - 1][j - 2v] + w,……, f[i - 1][j - sv] +(s - 1)w)

不能用完全背包问题来优化多重背包问题！！！

如何优化呢？

每个物品有s件，对每个物品进行二进制打包：

​ 设s = 1023(0,1,2,3,……,1023)

​ 把这些打包为：1，2，4，8，……，512

​ 则s = 200

如下情况：

1，2，4，8，16，32，64，73

除73外都是可以通过乘二凑出来的数，最后的73凑不出来，需要特判一下，再对剩下打包。

因此我们完成了对每个物品进行了打包，然后对每个包做01背包问题（需要乘上每个包中物品的数量）

#include <iostream>

using namespace std;

const int N = 2010;
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;

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

    cout<<f[m]<<endl;
    return 0;
}

多重背包问题Ⅲ

题目链接： https://www.acwing.com/problem/content/6/

思路：

二维数组：

对于第i类物品：

f[i][j] = max(f[i - 1][j],f[i - 1][j - 2v] + 2w,f[i - 1][j - 3v] + 3w,…,f[i - 1][j - sv] + sw)

f[i][j-v] = max(f[i-1][j-v],f[i-1][j-2v] + w,f[i-1][j-3v] + 2w,…,f[i-1][j-sv] + (s-1)w,f[i-1][j-(s+1)v]+sw)

f[i][j-2v] = max(f[i - 1][j - 2v],f[i - 1][j - 3v] + w,f[i - 1][j - 4v] + 2w,……,f[i - 1][j - sv] + (s - 2)w)

f[i][j - 3v] = ……………………………………

f[i][j - 4v] = ……………………………………

发现对于每一类物品，体积 j,j - v,j - 2v,j - 3v,……,可以分为j类 0 <= j < m

则有：

f[0],f[v],f[2v],f[3v],……,f[kv]（单调队列）

f[1],f[1 + v],f[1 + 2v],f[1 + 3v],……,f[1 + kv]（单调队列）

f[2],f[2 + v],f[2 + v],……,f[2 + kv]（单调队列）

.

.

f[j],f[j + v],f[j + 2v],……,f[j + kv]（单调队列）

对于每一类物品的按体积分的每一类，可以利用单调队列找最大值，因此问题就变成了j个单调队列的问题。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010;

int f[N],g[N],q[N];

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i = 1;i <= n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(g,f,sizeof f);
        for(int j = 0;j < v;j++)
        {
            int hh = 0,tt = -1;
            for(int k = j;k <= m;k += v)
            {
                if(hh <= tt && q[hh] < k - s * v) hh++;
                if(hh <= tt) f[k] = max(f[k],g[q[hh]] + (k - q[hh]) / v * w);
                while(hh <= tt && g[k] >= g[q[tt]] + (k - q[tt]) / v * w) tt--;
                q[++tt] = k;
            }
        }
    }

    cout<<f[m]<<endl;
    return 0;
}

分组背包问题

题目链接： https://www.acwing.com/problem/content/9/

状态表示：f[i][j]表示只从前i组物品中选，且总体积不大于j的所有选法

集合划分：

与完全背包问题的区别：

完全背包问题是枚举第i组物品选几个，分组背包问题是枚举第i组物品选哪个。

#include <iostream>

using namespace std;

const int N = 110;

int f[N],v[N][N],w[N][N],s[N];

int main()
{
    int n,m;
    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(j >= v[i][k])
                    f[j] = max(f[j],f[j - v[i][k]] + w[i][k]);
            }
        }
    }

    cout<<f[m]<<endl;
    return 0;
}

二维费用的背包问题

题目链接： https://www.acwing.com/problem/content/8/

思路：

费用1：体积

费用2：重量

价值：最大价值

状态表示：f[i][j][k]:在选到第 i个物品时，费用1不超过j，费用2不超过k的物品最大价值。

集合划分： 不选：f[i][j][k] = f[i - 1][j][k]

​ 选： f[i][j][k] = max(f[i][j][k],f[i - 1][j - v][k - m] + w)

三维优化成二维： f[V][M]

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];

int main()
{
    int n,V,M;
    cin>>n>>V>>M;

    for(int i = 0;i < n;i++)
    {
        int v,m,w;
        cin>>v>>m>>w;
        for(int j = V;j >= v;j--)
        {
            for(int k = M;k >= m;k--)
            {
                f[j][k] = max(f[j][k],f[j - v][k - m] + w);
            }
        }
    }

    cout<<f[V][M]<<endl;
    return 0;
}

采药（01背包）

题目链接： https://www.acwing.com/problem/content/425/

#include <iostream>

using namespace std;
const int N = 1010,M = 110;

int f[N],v[M],w[M];

int main()
{
    int m,n;
    cin>>m>>n;

    for(int i = 0;i < n;i++) cin>>v[i]>>w[i];

    for(int i = 0;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]<<endl;
    return 0;
}

装箱问题（01背包）

题目链接： https://www.acwing.com/problem/content/1026/

价值就是体积！！！

#include <iostream>

using namespace std;

const int N = 20010, M = 35;

int f[N],v[M];

int main()
{
    int n,m;
    cin>>m>>n;

    for(int i = 0;i < n;i++) cin>>v[i];

    for(int i = 0;i < n;i++)
    {
        for(int j = m;j >= v[i];j--)
        {
            f[j] = max(f[j],f[j - v[i]] + v[i]);
        }
    }

    cout<<m - f[m]<<endl;
    return 0;
}

宠物小精灵之收服(二维费用背包问题)

题目链接： https://www.acwing.com/problem/content/1024/

思路：

二维费用背包问题：

费用1：精灵球数量

费用2：对皮卡丘造成的伤害

价值：精灵数量(选或不选0或1)

状态表示：f[i][j][k]:在选到第 i个物品时，费用1不超过j，费用2不超过k的物品最大价值。

集合划分： 不选：f[i][j][k] = f[i - 1][j][k]

​ 选： f[i][j][k] = max(f[i][j][k],f[i - 1][j - v1][k - v2] + 1)

三维优化成二维： f[V1][V2]

#include <iostream>

using namespace std;
const int N = 1010,M = 510;

int f[N][M],w[N],v[M];

int main()
{
    /*费用1最大容量：V1
      费用2最大容量：V2
      物品数量：n
    */
    int V1,V2,n;
    cin>>V1>>V2>>n;

    for(int i = 0;i < n;i++)
    {
        int v1,v2;
        cin>>v1>>v2;

        for(int j = V1;j >= v1;j--)
        {
            for(int k = V2;k >= v2;k--)
            {
                f[j][k] = max(f[j][k],f[j - v1][k - v2] + 1);
            }
        }
    }
    cout<<f[V1][V2 - 1]<<" ";//第二维是皮卡丘所用掉的体力，最后体力要保留1，体力不能为0
                             //皮卡丘的满体力值是V2，用掉的体力值是（V2 - 1），若用掉的体力值是V2
                             //则皮卡丘体力为0,不能捕获精灵，所以最终状态是f[V1][V2 - 1]
    int k = V2;
    while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;//枚举最终状态消耗了多少体力值，总体力减去消耗体力值即为最终答案
    cout<<V2 - k<<endl;
    return 0;
}

数字组合（01背包求方案数）

题目链接： https://www.acwing.com/problem/content/280/

思路：

状态表示： f[i][j] 表示选第i个数时，他们的和恰好为j的方案数

集合划分： 不选： f[i][j] = f[i - 1][j]

​ 选： f[i][j] += f[i - 1][j - v[i]]

#include <iostream>

using namespace std;
const int N = 110,M = 10010;

int f[M],v[N];

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i = 1;i <= n;i++) cin>>v[i];


    f[0] = 1;
    for(int i = 1;i <= n;i++)
    {
        for(int j = m;j >= v[i];j--)
        {
            f[j] += f[j - v[i]];
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

潜水员(二位费用背包”至少“情况)

题目链接： https://www.acwing.com/problem/content/1022/

思路：

状态表示： f[i,j,k]:所有从前i个物品中选,且氧气含量至少是j,氮气含量至少是k的所有选法的气缸重量总和的最小值

集合划分： 选：f[i - 1][j][k]

​ 不选： f[i - 1][j - v1][k - v2]

初始化：求最小值，初始化为INF

​ f[0][0][0] = 0从实际意义出发，从前0个物品中选，氧气含量 >= j,氮气含量 >= k的最小值为0。

可以抽象为：

状态表示： f[i,j,k]:所有从前i个物品中选,且体积至少是j,重量至少是k的所有选法的最小价值

集合划分： 选：f[i - 1][j][k]

​ 不选： f[i - 1][j - v1][k - v2]

初始化：求最小值，初始化为INF

​ f[0][0][0] = 0从实际意义出发，从前0个物品中选，体积 >= j,重量 >= k的最小价值为0。

我们求至少需要的体积和重量，f[j][k]表示至少需要j个体积，k个重量，对每一个物品i的体积为v，重量为m

如果选这个物品：

​ 若j <= v,则说明至少需要j个体积等价于至少需要0个体积

​ 若k<=m,则说明至少需要k个重量等价于至少需要0个重量

则有如下四种情况：

​ ①j <= v && k <= m

​ ②j <= v

​ ③k <= m

​ ④j >= v && k >= m

与朴素01背包不同的是：

普通的01二维背包：体积至多为j，重量至多为k

已经规定的容量为j和k,则取用物品的体积v和重量m：

j >= v && k >= m

此题的01二维背包：体积至少为j，重量至少为k

需要的容量为j和k，则取用物品的体积v和重量m

有容量小于取用物品容量的情况：

j <= v && k <= m

j <= v

k <= m

有容量都大于取用物品容量的情况：

j > v && k > m

对于最大值最小值初始化的总结：
二维情况
1、体积至多j，f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）
2、体积恰好j，
当求价值的最小值：f[0][0] = 0, 其余是INF
当求价值的最大值：f[0][0] = 0, 其余是-INF
3、体积至少j，f[0][0] = 0，其余是INF（只会求价值的最小值）

一维情况
1、体积至多j，f[i] = 0, 0 <= i <= m（只会求价值的最大值）
2、体积恰好j，
当求价值的最小值：f[0] = 0, 其余是INF
当求价值的最大值：f[0] = 0, 其余是-INF
3、体积至少j，f[0] = 0，其余是INF（只会求价值的最小值）

求方案数初始化总结
二维情况
1、体积至多j，f[0][i] = 1, 0 <= i <= m，其余是0
2、体积恰好j，f[0][0] = 1, 其余是0
3、体积至少j，f[0][0] = 1，其余是0

一维情况
1、体积至多j，f[i] = 1, 0 <= i <= m，
2、体积恰好j，f[0] = 1, 其余是0
3、体积至少j，f[0] = 1，其余是0

作者：小呆呆
总结参考链接： https://www.acwing.com/blog/content/458/

朴素代码如下：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 50,S = 160;

int f[N][S];

int main()
{
    int n,v,m;
    cin>>v>>m>>n;

    memset(f,0x3f,sizeof f);
    f[0][0] = 0;
    for(int i = 0;i < n;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        for(int j = v;j >= 0;j--)
        {
            for(int k = m;k >= 0;k--)
            {
                if(j <= a && k <= b)
                {
                    f[j][k] = min(f[j][k],f[0][0] + w);
                }
                else if(j <= a)
                {
                    f[j][k] = min(f[j][k],f[0][k - b] + w);
                }
                else if(k <= b)
                {
                    f[j][k] = min(f[j][k],f[j - a][0] + w);
                }
                else if(j > a && k > b)
                {
                    f[j][k] = min(f[j][k],f[j - a][k - b] + w);
                }
            }
        }
    }
    cout<<f[v][m]<<endl;
    return 0;
}

对代码进行优化：

j <= a: (j - a) <= 0就选0

j > a:(j - a) > 0就选(j - a)

可得max(0,j - a)

同理可得max(0,k - b)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 25,M = 80;
int f[N][M];
int main()
{
    int m,n;
    cin>>m>>n;

    int k;
    cin>>k;
    memset(f,0x3f,sizeof f);
    f[0][0] = 0;
    for(int i = 0;i < k;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;

        for(int j = m;j >= 0;j--)
        {
            for(int k = n;k >= 0;k--)
            {
                f[j][k] = min(f[j][k],f[max(0,j - a)][max(0,k - b)] + c);
            }
        }
    }
    cout<<f[m][n]<<endl;
    return 0;
}