数据结构与算法学习笔记(Acwing提高课)----动态规划·背包模型(二)

数据结构与算法学习笔记----动态规划·背包模型(二)

@@ author: 明月清了个风
@@ first publish time: 2025.5.1

ps⭐️这一篇是背包模型二，主要是多重背包这一分支的题目。在基础课中已经讲解过多重背包 I与多重背包II ，链接在这，为了方便，这里也直接将这两道题的内容复制过来了(题目中有标记)，也可以去看原来的复习。其实就是两道题，一道是滑动窗口优化的多重背包，一道是多重背包的应用题。

Acwing 4. 多重背包问题 I （基础课）

有$N$件物品和一个容量是$V$的背包。

第$i$件物品最多有$s_i$件，每件体积是$v_i$，价值是$w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行包含两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有$N$行，每行两个整数$v_i,w_i,s_i$，用空格隔开，分别表示第$i$件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0\le N,V\le 100$,

$1\le v_i,w_i,s_i\le 100$

思路

和上面两题一样，只是又多了一个限制条件——每件物品的数量是有限的，因此同样使用上面的思路。

对于状态表示f[i][j]表示所有从前i个物品中选，并且总体积不超过j的选法中价值最大的。

对于状态转移，同样根据第i个物品的选择情况——可以分为选$0,1,\cdots ,s_i$个，因此状态转移方程和完全背包问题完全一样:

f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i]) (k = 0,1,2,..., s[i])

由此，我们可以给出以下代码：

#include <iostream>
#include <cstdio>using namespace std;const int N = 110;int n, m;
int f[N][N];
int v[N], w[N], s[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 - k * v[i]] + k * w[i]);cout << f[n][m] << endl;return 0;
}

同样的，观察状态转移方程可以发现，每次更新使用的都是i - 1层的结果，因此可以使用滚动数组优化，降低空间复杂度，这里需要注意的是对于体积j需要进行倒序遍历，理由和01背包中一样。

#include <iostream>
#include <cstdio>using namespace std;const int N = 110;int n, m;
int f[N];
int v[N], w[N], s[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 = m; j >= v[i]; j --)for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);cout << f[m] << endl;return 0;
}

这里会出现一个问题，是否还可以像完全背包那样优化状态转移方程，也就是将三重循环优化到两重循环。

答案是不可以。对于完全背包中的优化，我们是通过对比了两个状态的表达式得到的，可以优化的前提是两个表达式内容完全相同，但是在这一题中并不一定，因为我们的数量是有限制的，这就导致两个表达式的项数其实可能会不一样，我们可以来对比一样f[i][j]和f[i][j - v[i]]的表达式，下面就把完全背包中的两个表达式列出
$$\begin{gathered} f_{i,j}=max(f_{i-1,j},f_{i-1,j-v}+w,f_{i-1,j-2v}+2w,\cdots ,f_{i-1,j-kv}+kw) \\ {f}_{i,j-v}=max(f_{i-1,j-v},f_{i-1,j-2v}+w,\cdots ,f_{i-1,j-kv}+(k-1)w) \end{gathered}$$
在这一题中，看似第二个表达式加上$w$就是第一个表达式的后面部分，但是要考虑到一个情况，就是**$f_{i,j-v}$的体积j - v仍能装下所有的$k$个物品**。

换一种说法可能会更好理解，第二个表达式$f_{i,j-v}$中的$j-v$的中的$v$并不是为一个第$i$件物品预留的，而在第一个表达式中的所有涉及到$-v$的项，这些体积$v,2v,3v,\cdots ,kv$，这些的含义都是为$k$个第$i$件物品预留位置。因此，第二个表达式虽然预先减去了一个体积$v$，但是他最后可能还多一项$f_{i,j-v-kv}+kw$，因为体积$j-v$仍可能装下所有的$k$件第$i$个物品，而这多的一项是不可能出现在第一个表达式中的。

Acwing 5. 多重背包问题 II（基础课）

有$N$件物品和一个容量是$V$的背包。

第$i$件物品最多有$s_i$件，每件体积是$v_i$，价值是$w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行包含两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有$N$行，每行两个整数$v_i,w_i,s_i$，用空格隔开，分别表示第$i$件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0\le N\le 1000$,

$0\le V\le 2000$

$1\le v_i,w_i,s_i\le 2000$

思路

这一题也是多重背包，但是相对于上一题来说，数据范围发生了很大的变化，观察上一题的代码可以发现主要代码是三重循环，如果用到这一题来的话就是$40$亿，一定超时，因此需要进行优化。

这里我们用到的优化方式是二进制优化，其实这个思路我们之前已经学过了，在快速幂中，如果没有学过或者忘了，可以先去看一下，是非常类似的思想。我们可以在$\log n$的复杂度上枚举$n$级别的数，下面我们来看具体怎么优化。

先举个例子，假设我们有$200$个物品，那么我们可能的拿取方式就是$0,1,2，\cdots ，200$个物品，也就是$201$种取法，需要枚举$201$次，但是如果我们通过二进制打包，也就是将物品看成$0,1,2,4，\cdots ,64$个物品，我们就能通过这些打包过的凑出$0\sim 127$的所有数，这时将最后一份打包成$73$个，那么就能凑出$0\sim 200$的所有数。

为啥能凑出这些数，我们用更小的范围举例，如用$0,1,2$，我们就能凑出$0\sim 3$，那么加上一个$2^2=4$，我们就能凑出$0\sim 7$，同理继续向上累加即可，我们用$2^1,2^2,\cdots ,2^k$可以凑出$0\sim 2^k-1$中的所有数，那么假设我们要凑的是$s$，我们需要的就是$2^1,2^2,\cdots ,2^k$，其中$2^k$应满足$2^1+2^2+\cdots +2^k<s$并且$2^1+2^2+\cdots +2^k+2^{k+1}>s$。

此时我们需要用到的所有数就是$2^1,2^2,\cdots ,2^k,s-(2^1+2^2+\cdots +2^k)$，

我们将每个物品都这样处理后，将可以将多重背包问题转化为$01$背包问题，对于打包过后的每个物品的数量拿与不拿的方案等价于打包前拿多少个每个物品的方案，下面就看代码吧，这里直接使用了$01$背包问题滚动数组优化过的代码：

#include <iostream>
#include <cstdio>using namespace std;const int N = 25000, M = 2010;int n, m;
int v[N], w[N];
int f[M];int main()
{cin >> n >> m;int cnt = 0;  // 记录转化后一共有多少个物品。for(int i = 0; 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;}if(s > 0)  // 最后剩下的打包在一起{cnt ++;v[cnt] = a * s;w[cnt] = b * s;}}for(int i = 1; i <= cnt; 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;
}

Acwing 6. 多重背包问题III

有$N$件物品和一个容量是$V$的背包。

第$i$件物品最多有$s_i$件，每件体积是$v_i$，价值是$w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行包含两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有$N$行，每行两个整数$v_i,w_i,s_i$，用空格隔开，分别表示第$i$件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0\le N\le 1000$,

$0\le V\le 20000$

$1\le v_i,w_i,s_i\le 20000$

思路

相较于前两题来说，第三题的数据范围进一步扩大，因此要进一步优化做法。

在上一题中，仅仅对比了$f[i][j]$与$f[i][j-v]$的表达式之间的区别，进一步地，将$f[i][j-2v]、f[i][j-3v]、\cdots 、f[i][j-kv]$的表达式进行对比。这些值的第二维为所有模$v$具有相同值的数，因此可以将它们先设出来。设模$v$余数为$r$，则这些下标为$r,r+v,r+2v,\cdots ,j-3v,j-v,j$。

根据之前题目中的分析，$f[i][j]$的状态计算为：
$$f[i][j]=\max (f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,\cdots ,f[i-1][j-sv]+sw)$$
其中$s$就是该物品的数量，该式在理想情况下共有$s+1$项

继续写出$f[i][j-v]$的状态计算方程
$$f[i][j-v]=\max (f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,\cdots ,f[i-1][j-sv]+(s-1)w,f[i-1][j-(s+1)v]+sw)$$
上式在理想情况下共有$s+1$项，继续写出$f[i][j-2v]$，$f[i][j-3v]$等等表达式可以发现同样的规律，而每个表达式中的$s+1$项就是在该表达式下标开始处向前的$s+1$项加上对应的偏移量$kw$，比如，对于$f[i][j]$就是$f[i-1][j]+0w$，$f[i-1][j-v]+w$,$\cdots$这$s+1$项。

也就是说，每次求最大值都是在同样的窗口长度的项中求一个最大值，因此可以使用滑动窗口进行处理。当然，上面说了这是理想情况，因为$j$的大小是有限的，比如$j-sv$可能并不是合法下标，但这并不影响这个结论，仅代表此时滑动窗口中项数不足而已，只需要进行特判即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 20010;int n, m;
int f[N], g[N], q[N];int main()
{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[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;q[++ tt] = k;}}}cout << f[m] << endl;return 0;
}

Acwing 1019. 庆功会

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输入格式

第一行两个数$n，m$，其中$n$代表希望购买的奖品的种数，$m$表示拨款金额。

接下来$n$行，每行$3$个数，$v,w,s$分别表示第$i$种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买$0$件到$s$件均可）

输出格式

输出一个整数，表示最大价值。

数据范围

$n\le 500$,$m\le 6000$

$v\le 100$,$w\le 1000$, $s\le 10$

思路

这一题就是简单的多重背包应用题，并且数据范围也不大，直接用最简单的多重背包版本就行啦。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 6010;int n, m;
int f[N];int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++){int v, w, s;cin >> v >> w >> s;for(int j = m; j >= 0; 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;
}