第一章 动态规划(3)：背包模型

目录

• 一、基础模型
• • 1.1、01背包问题
  • 1.2、完全背包问题
  • 1.3、多重背包问题 I
  • 1.4、多重背包问题 II ——二进制优化
  • 1.5、多重背包问题 III ——滑动窗口优化
  • 1.6、分组背包
  • 1.7、有依赖的背包问题
  • 1.8、混合背包问题
  • 1.9、二维费用背包问题
  • 1.10、背包问题求具体方案——字典序最小的方案数
  • 1.11、背包问题求方案数——最大价值的方案数

背包问题

时间复杂度

DP时间复杂度 = 状态数量 x 转移的计算量

一、基础模型

• 01背包问题：每件物品只有一个，故每件物品最多只能用一次，即被称为01背包；
• 完全背包问题：每件物品有无限个；
• 多重背包问题：每件物品的数量不同（多重背包问题是分组背包问题的特例）；
• 分组背包：物品分为n组，每组里面有若干个，但每组里面只能选择一个物品。

1.1、01背包问题

ACWing 2

每件物品只有一个，故每件物品最多只能用一次，即被称为01背包。

集合
f[i, j]：从前i个物品中选择，总体积小于等于j的选法的价值最大值

集合划分
f[i - 1, j]：从第1个到第 i - 1 个物品中选择，总体积不超过 j 的选法的价值最大值
f[i - 1, j - v[i]] + w[i]：从第1个到第 i - 1 个物品中选择，但总体积不超过 j - v[i] + 第i个物品价值的选法的价值最大值

状态表示
二维状态表示：f[i, j] = max(f[i - 1, j], f[i - 1, j - v[i]] + w[i])
二维变一维： f[j] = max(f[j], f[j - v[i]] + w[i]);（注意for循环是从大到小）

状态初始化
f[0, j] = 0：取0件物品且体积不超过j的取法的价值最大值。

方法一：二维状态表示

#include 
#include 

using namespace std;

const int N = 1010;

int n, m; // n表示背包的个数，m表示背包的容量
int v[N], w[N]; // v表示物品体积，w表示物品价值
int f[N][N]; // 表示物品状态

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    // f[0][0 ~ m]：考虑0件物品总体积不超过m的最大价值都是0
    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]) // 背包要能容下第i个物品体积j
            	f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
        
    cout << f[n][m] << endl;
    
    return 0;
}

方法二：二维状态优化成一维

• 因为f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])中f[i] 只会使用f[i - 1]，对f(i - 2)到f(0)是没有使用的，所以可以使用滚动数组；
• 对于f[i-1][j]与f[i-1][j-v[j]] 中的f[i][j]的j这一层，其值均<= j，没有在j的两侧，所以可以使用一维数组来计算。

优化过程：

• 对代码第10行、第22行删除f[N][N]中的第一维，所以第10行代码变成int f[N];，第22行代码变成f[j] = f[j]，因此这行代码可以直接删除；
• 对代码第23行，因为j要在j >= v[i]才会生效，所以第20行代码可以修改成for (int j = v[i]; j <= m; j ++ )，同时第23行的if判断条件可以删除了；
• 对代码f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])，如果直接将f[N][N]中的第一维删除，即变成f[j] = max(f[j], f[[j - v[i]] + w[i])后，它与我们原来的代码不是等价的！ 首先，j - v[i] < j，我们在使用删除后的式子进行计算的时候，由于j是从小到大枚举的，当我们算到f[j]的时候，j - v[i]就已经被计算过了，所以删除后的式子其实是等价于f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i])。所以对于j的循环，需要从大到小循环。

这个过程还可以听一听提高课的背包模型(二)一节 2:10:00 开始的优化过程，那里也会讲解。

#include 
#include 

using namespace std;

const int N = 1010;

int n, m; // n表示背包的个数，m表示背包的容量
int v[N], w[N]; // v表示物品体积，w表示物品价值
int f[N]; // 表示物品状态

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    // f[0][0 ~ m]：考虑0件物品总体积不超过m的最大价值都是0
    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;
}

更简单的写法

#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; 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] << endl;
    
    return 0;
}

1.2、完全背包问题

ACWing 3

每件物品有无限个可供使用。

集合
f[i, j]：所有只考虑前 i 个物品，且总体积不大于 j 的所有选法的价值最大值

集合划分
按第i类物品最多选择k个来划分：

• 当k = 0时，f[i - 1, j]，表示从i - 1的物品中每种最多选择k件物品，且使其体积不大于j的选法价值最大值；
• 当k != 0时，f[i - 1, j - k * v[i]] + k * w[i]，表示从前i - 1个物品中每种物品最多选择k件，且使其体积不大于j - k * v[i]+ 最多选择k件第i件物品的选法的价值最大值
  

状态表示
三重循环：f[i, j] = max(f[i, j], f[i - 1, j - v[i] * k] + k * w[i]);
二重循环：f[i, j] = max(f[i - 1, j], f[i, j - v[i]] + w[i]);（注意for循环是从小到大，与01背包优化分开 + 优化思路）
二维变一维：f[j] = max(f[j], f[j - v[i]] + w[i]);（注意for循环是从小到大，与01背包优化分开）

方法一：二维状态表示

会TLE！

#include 
#include 

using namespace std;

const int N = 1010;

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

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] + k * w[i]);
                
                
    cout << f[n][m] << endl;
    
    return 0;
}

方法二：将三重循环优化成二重循环

优化思路：

#include 
#include 

using namespace std;

const int N = 1010;

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

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;
}

方法三：将二维优化为一维

#include 
#include 

using namespace std;

const int N = 1010;

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

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 = v[i]; j <= m; j ++ ) // 枚举物品体积
        {
            
            
            
            
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
                
    cout << f[m] << endl;
    
    return 0;
}

更简单的写法

#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int f[N];

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] << endl;
    
    return 0;
}

1.3、多重背包问题 I

ACWing 4

每件物品可供使用的数量不同。多重背包问题是分组背包问题的特例。

集合
f[i, j]：所有只从前i个物品中选择且总体积不超过j的选法的价值最大值

集合划分
按从第i个物品中选k个物品，最多选择s[i]个物品来划分

状态计算
三重循环：f[i, j] = max(f[i, j], f[i - 1, j - v[i] * k] + k * w[i]);（与完全背包问题类似，只是第三从循环的判断条件增加了）

三重循环，与完全背包方法一类似

#include 
#include 

using namespace std;

const int N = 110;

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

int main()
{
    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 - v[i] * k] + w[i] * k);
                
    cout << f[n][m] << endl;
    
    return 0;
}

更简洁的写法

#include 

using namespace std;

const int N = 110;

int n, m;
int f[N];

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

1.4、多重背包问题 II ——二进制优化

ACWing 5

优化思路：对每一个物品的数量进行二进制优化

时间复杂度： 从O(nvs)降到了O(nvlogs)

二进制优化枚举的思路简介：假设一个数s = 1023，即物品有1023个，那么我们在上面枚举的时候就会从k = 0 ~ 1023。现在换个思路，将若干个物品打包一块考虑，这里将其打包成10组，每组分别有1、2、4、8、16、32、64、128、256、512个物品，每次每组最多只能选择1个物品，那么这从这10组中选择出的10个数便能表示出1 ~ 1023中的任意一个数。比如：

• 只有1时，便能表示出1；
• 加上2后，1、2两个数便能表示出1~3；
• 加上4后，1、2、4三个数便能表示出1~7；

以此类推，便能表示出1 ~ 1023的所有数。
对于每一组，我们可以将其看成是01背包问题，每次只选择一个，用10个新的物品可以表示出我们原来的所有物品，时间复杂度从n降为了logn（比如log(1024) = 10）。给定一个物品数量s，就可以将其拆分成logs个分组。

注意：log的底数是2。

当s是一个一般的数时，如 s = 200的时候，每组数据就为1、2、4、8、16、32、64、73 { 其中 73 = 200 - (63 + 64) = 200 - 127}，这里最后一组若取128，则总共就能表示到1 ~ 256，大于了200。

我们这里将每种物品的数量变成logs[i]组，所以对于v[N]、w[N]的下标1, 2, 3, ..., logs[1], logs[1] + 1, ... , logs[1] + logs[2], ...，这里说明前logs[1]个下标上的值，分别代表将第一件物品的数量s[1]分成1、2、4、8...件，后面就代表将第二件物品分成若干组的情况。

整体来看，就是将每个物品的数量分成都若干组，总共有cnt组。在这cnt组中，每组只能选择一个数值，就类比01背包问题了。

#include 
#include 

using namespace std;

const int N = 12000, M = 2010; // 物品个数是N*S=2e6(N=1000, S=2000), 优化后最多N*logS(向上取整后) 

int n, m; // n是物品种类，m是背包容量
int v[N], w[N];
int f[M];

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; // k代表每组物品数量
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k; // k个物品打包在一起，它的体积就是a*k
            w[cnt] = b * k; // 更新价值
            s -= k;
            k *= 2;
        }
        
        if (s > 0) // 最后还有剩余
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;
    
    // 01背包问题
    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;
}

更简洁的写法

#include 

using namespace std;

const int N = 12000, M = 2010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2)
        {
            // 这里面直接看成01的代码来理解，k*v就是一个物品体积
            for (int j = m; j >= k * v; j -- )
                f[j] = max(f[j], f[j - k * v] + k * w);
            s -= k;
        }
        
        if (s)
            for (int j = m; j >= s * v; j -- )
                f[j] = max(f[j], f[j - s * v] + s * w);
    }
    
    cout << f[m] << endl;
    
    return 0;
}

1.5、多重背包问题 III ——滑动窗口优化

ACwing 6

优化思路：按完全背包问题的优化思路来

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-1, j-sv]+sw

// 完全背包问题是每种物品有无限个，多重背包问题是每种物品有s个，所以这里最后一项与上一行式子不同
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]
f[i, j-3v]
...

j-v, j-2v, j-3v...都是j模v的余数相同的点，即r = j % v，所以对于r < v[i]的，在数轴上表示有

由第一个式子，f[i, j]实质上是求从j-v开始，往后连续s个数的最大值；当我们求f[i, j-v]的时候，同样从f-2v开始，往后连续s个数的最大值；后面依次类推。比如s=3时，反映在数轴上就是

注意：若前面的数不足s个的时候，就需要特判一下，有多少算多少。

于是，由上面的规律，每次求一个f[i, j-kv]都相当于是在其前面s个数中的最大值 + 一个偏移量w，这就转换成了求在滑动窗口中的最大值。

这个题真的难理解，当然不是指思路，指代码。找到一篇好的题解，代码都是参考它的，它里面公式推的很详细，根据公式慢慢看代码，就容易懂了。

二维朴素版本

#include 

using namespace std;

const int N = 1010, M = 20010;

int n, m; // n是物品数量，m是背包容量
int v[N], w[N], s[N]; // 物品体积，物品价值，物品数量
int f[N][M];
int q[M]; // 单调队列

int main()
{
    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 r = 0; r < v[i]; ++ r) // 枚举余数
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

拷贝数组的优化版本：

#include 
#include 

using namespace std;

const int N = 1010, M = 20010;

int n, m; // n是物品数量，m是背包容量
int v[N], w[N], s[N]; // 物品体积，物品价值，物品数量
int f[M], g[M]; // g存储的f[i-1][j]层的状态
int q[M]; // 单调队列

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i) // 枚举每个物品
    {
        memcpy(g, f, sizeof g);
        for (int r = 0; r < v[i]; ++ r) // 枚举余数
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j]) -- tt;
                q[ ++ tt] = j;
                f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

滚动数组的优化版本

#include 
#include 

using namespace std;

const int N = 1010, M = 20010;

int n, m; // n是物品数量，m是背包容量
int v[N], w[N], s[N]; // 物品体积，物品价值，物品数量
int f[2][M];
int q[M]; // 单调队列

int main()
{
    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 r = 0; r < v[i]; ++ r) // 枚举余数
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

省去V、W、S数组空间的写法（只写一种优化方法的，这里是滚动数组优化的简写）

#include 
#include 

using namespace std;

const int N = 1010, M = 20010;

int n, m; // n是物品数量，m是背包容量
int f[2][M];
int q[M]; // 单调队列

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) // 枚举每个物品
    {
        int v, w, s;
        cin >> v >> w >> s;
        for (int r = 0; r < v; ++ r) // 枚举余数
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v)
            {
                while (hh <= tt && j - q[hh] > s * v) hh ++ ;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v * w <= f[(i - 1) & 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v * w;
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

1.6、分组背包

ACWing 9

物品分为n组，每组里面有若干个，但每组里面只能选择一个物品。

集合
f[i, j]：只从第i组物品中选择，且总体积不大于j的所有选法的价值的最大值

集合划分（选哪个）

• 从第i组物品中选择第0件物品，即一个都不选：f[i - 1, j]
• 从第i组物品中选择第k件物品，则：f[i - 1, j - v[i, k]] + w[i, k]
  

状态计算
二维状态：f[i, j] = max(f[i - 1, j], f[i - 1, j - v[i][k]] + w[i][k]);
一维状态：f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);（注意for循环是从大到小）

未优化版本：

#include 
#include 

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N]; //每个物品的体积和价值以及每组物品个数
int f[N][N];

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 ++ ) // 枚举第i种物品的每个物品
                if (j >= v[i][k]) // 这个if不能放进上面第三个for循环里面去
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
        
    cout << f[n][m] << endl;
    
    return 0;
}

优化版本：

#include 
#include 

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N]; //每个物品的体积和价值以及每组物品个数
int f[N];

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 ++ ) // 枚举第i种物品的每个物品
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    
    cout << f[m] << endl;
    
    return 0;
}

几个背包问题的状态分析区别：

• 完全背包：枚举第i个物品选几个；
• 多重背包：枚举第i个物品选几个；
• 分组背包：枚举第i组物品选哪个，或者不选。

1.7、有依赖的背包问题

ACwing 10

集合
f[u, j]：从所有以u为根的子树中选择，且总体积不超过j的方案数的价值最大值

集合划分
每棵树按子树划分，每棵子树按体积划分（PS：金明的预算方案是按方案来划分的，因为那个题目方案数很小，这个题如果按照方案数来划分，子树下面的情况有 2^n 种，太多无法保存）。每棵子树内部就是一个分组背包问题。

树的存储：使用数组模拟邻接表存储

#include 
#include 
#include 

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N]; // 每个物品的体积与价值
int h[N], e[N], ne[N], idx;
int f[N][N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
	// 这里其实就是一个分组背包问题
    for (int i = h[u]; i != -1; i = ne[i]) // 循环物品组
    {
        int son = e[i];
        dfs(e[i]);
       
        for (int j = m - v[u]; j >= 0; j -- ) // 循环体积
            for (int k = 0; k <= j; k ++ ) // 这里每个分组里面是按体积划分的，所以这里取哪一个物品就是枚举每一种体积
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }
    
    // 将物品u加进去
    for (int i = m; i >= v[u]; i -- )
        f[u][i] = f[u][i - v[u]] + w[u];
        
    // 清空剩余部分
    for (int i = 0; i < v[u]; i ++ )
        f[u][i] = 0;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int root; // 记录根结点
    for (int i = 1; i <= n; i ++ )
    {
        int p; // 每个结点依赖的结点
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i; // 根结点
        else add(p, i);
    }
    
    dfs(root);
    
    cout << f[root][m] << endl;
    
    return 0;
}

1.8、混合背包问题

ACwing 7

多种背包问题混合在一起

• 状态表示：f[i, j]
• 集合：只从前i个物品中选择，且总体积不超过j的选法的价值最大值
• 状态计算：
  • 01背包问题：f[i, j] = max(f[i - 1, j], f[i - 1, j - v[i]] + w[i])
  • 完全背包问题：f[i, j] = max(f[i - 1, j], f[i, j - v[i]] + w[i])
  • 多重背包问题：f[i, j] = max(f[i - 1, j], f[i - 1, j - v[i] * k] + w[i] * k)

算法思路

由题意，这个题目仅限制了“有N种物品和一个容量是V的背包”，所以在对第i个物品进行状态计算的时候，第i个物品的种类与前面i-1个物品种类无关。因此在计算第i件物品的时候，只需要根据第i个物品是什么类型的背包问题，就是用什么类型的状态转移方程。

为了考虑时间复杂度，多重背包要使用二进制优化（01背包问题是一种特殊的[每个物品仅有一件]多重背包问题）

#include 
#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == 0) // 完全背包问题
            for (int j = v; j <= m; j ++ )
                f[j] = max(f[j], f[j - v] + w);
        else // 01背包或者多重背包
        {
            if (s == -1) // 如果是01背包，转换为多重背包问题
                s = 1;
                
            // 多重背包问题——二进制优化
            for (int k = 1; k <= s; k *= 2)
            {
                for (int j = m; j >= k * v; j -- )
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            
            if (s) // s还有剩余
                for (int j = m; j >= s * v; j -- )
                    f[j] = max(f[j], f[j - s * v] + s * w);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

1.9、二维费用背包问题

ACwing 8

二维费用背包问题不仅可以和01背包问题结合，也可以和完全背包、多重背包、分组背包问题结合在一块。本题是和01背包问题结合在一起的。

集合

f[i, j, k]：所有制从前i个物品中选，并且总体积不超过j，总重量不超过k的选法

集合划分

• 左：所有不包含i的选法，只从1 ~ i-1中选择
• 右：所有包含i的选法

状态计算

• 左：f[i-1, j, k]
• 右：f[i-1, j-vi, k-mi] + wi

#include 

using namespace std;

const int N = 110;

int n, V, M;
int f[N][N];

int main()
{
    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;
}

1.10、背包问题求具体方案——字典序最小的方案数

ACwing 12

先求出价值，然后找方案。

以01背包问题为例，01背包问题状态转移方程：f[i, j] = max(f[i-1, j], f[i-1, j-vi] + wi)。所谓求具体方案，其实就是判断出每个物品是否被选，实质是最短路问题求路径，反推当前状态是从哪一个状态转移过来的。

下面参考了这里的题解。

由于题目要求求出字典序最小的方案，如果存在一个包含第1个物品的方案，那么为了确保字典序最小，第1个物品必然要选择。接下来的问题就转换成了从第2...N个物品中取寻找最优解。由之前的f[i, j]表示为从前i个物品中选择且体积不超过j的最优解，现在将f[i, j]修改为从第i个元素到最后一个元素中选择，且体积不超过j的最优解。于是便有了下面状态计算：

f[i, j] = max(f[i + 1, j], f[i + 1, j - vi] + w[i])

• 前面一种表示不选择第i件物品，那么最优解便是从第i+1件物品到最后一件物品中寻找的且总体积不超过j的选法；
• 后面一种表示选择第i件物品，那么最优解就是从第i+1件到最后一件物品中选择，且总体积不超过j - vi的选法。

字典序最小问题的解决方法——贪心

由上面的状态定义，f[1, m]一定是最大值，现在考虑第1个点能否选择：

• 如果f[1, m] = f[2, m - v[1]] + w[1]，说明选取了第1个物品是可以得到最优解的；
• 如果f[1, m] = f[2, m]，说明不选择第1个物品依然可以得到最优解；
• 如果f[1, m] = f[2, m] = f[2, m - v[1]) + w1，说明选择或者不选择第1个物品都能得到最优解，但是为了使字典序最小，第1件物品依然要选择。

#include 

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) // 必须先读入，读入不能放进循环内部
    	cin >> v[i] >> w[i];
    
    for (int i = n; i >= 1; 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]);
        }

    // f[1][m] 是最大值
    
    int j = m;
    for (int i = 1; i <= n; i ++ )
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            cout << i << ' ';
            j -= v[i];
        }
    
    return 0;
}

1.11、背包问题求方案数——最大价值的方案数

ACwing 11

f[i, j]：体积恰好是j的方案数
g[i, j]：f[i, j]取最大值的方案数

状态计算

• 左边：f[i-1, j]
• 右边：f[i-1, j-vi]+wi
• 如果左边大，则记录g[i-1, j]
• 如果右边大，则记录g[i-1, j-vi]
• 如果左边右边一样大，则记录g[i-1, j] + g[i-1, j-vi]

#include 
#include 

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n,m;
int f[N], g[N];

int main()
{
    cin >> n >> m;
    
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    g[0] = 1;
    
    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- )
        {
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if (maxv == f[j]) cnt += g[j];
            if (maxv == f[j - v] + w) cnt += g[j - v];
            g[j] = cnt % mod;
            f[j] = maxv;
        }
    }
    
    int res = 0;
    for (int i = 0; i <= m; i ++ )
        res = max(res, f[i]);
        
    int cnt = 0;
    for (int i = 0; i <= m; i ++ )
        if (res == f[i])
            cnt = (g[i] + cnt) % mod;
            
    cout << cnt << endl;
    
    return 0;
}