今日复习的内容是背包问题。
记得动态规划问题的初始化。
AcWing3382.整数划分
解题思路
考虑到本题是将一个数划分为 \(2\) 的幂的和，而 \(2\) 的 \(i\) 幂是可以无限使用的，所有可以将该问题转化为一个完全背包问题，即背包容量是 \(j\)，物品的重量是 \(2^i\)。
- 状态表示：\(f[j]\) 表示 \(j\) 被划分的方案的集合，属性是方案数。
- 状态计算：对于 \(f[j]\)，是否使用 \(i\) (\(i\) 为 \(2\) 的次幂)划分，则 \(f[j]=f[j]+f[j-i]\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010, MOD = 1e9;
typedef long long LL;
int n;
int f[N]; // f[i]表示i的不同划分方案的集合，属性是方案数
int main()
{
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i *= 2)
for (int j = i; j <= n; j ++)
f[j] = (f[j] + f[j - i]) % MOD;
cout << f[n] << endl;
return 0;
}
AcWing2.01背包问题
解题思路
- 状态表示：\(f[i][j]\) 表示用前 \(i\) 个物品，装在容量为 \(j\) 的背包的方案，属性是最大价值。
- 状态计算：对于 \(f[i][j]\)，那么可以划分为使用第 \(i\) 个物品和不使用，即 \(f[i-1][j-v[i]]+w[i]\) 和 \(f[i-1][j]\)，二者取最大值。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d%d", &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]);
}
printf("%d", f[n][m]);
return 0;
}
AcWing3.完全背包问题
解题思路
- 状态表示：\(f[i][j]\) 表示使用前 \(i\) 个物品，装在容量为 \(j\) 的背包的方案集合，属性是最大价值。
- 状态计算：根据使用若干个物品来划分，那么 \(f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i][j-2*v[i]]+2* 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 - k * v[i]] + k * w[i]);
我们可以据此观察 \(f[i][j]\) 和 \(f[i][j-v[i]]\) 的状态计算的差别。
-
\(f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i][j-2*v[i]]+2* w[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-3*v[i]]+2* w[i],...)\)
可以看出 \(f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])\)，就可以从时间上优化。
这里空间上优化，去掉第一维即可。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d%d", &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]);
}
printf("%d\n", f[n][m]);
return 0;
}
AcWing9.分组背包问题
解题思路
- 状态表示：\(f[i][j]\) 使用前 \(i\) 组的物品装在背包容量为 \(j\) 的方案集合，属性为最大价值。
- 状态计算：对于第 \(i\) 组的 \(s[i]\) 个物品，我们要么选择其中一个，要么不选择，对于第 \(i\) 组的第 \(k\) 个物品，\(f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k]]+w[i][k])\)。
C++代码
#include <bits/stdc++.h>
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 = 1; 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;
}
AcWing6.多重背包问题III
解题思路
多重背包问题，根据数据范围，依次使用朴素的三层循环做法，二进制优化为 \(O(n^2)\) \(01\) 背包问题以及单调队列优化。
考虑第 \(i\) 个物品，\(f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],...,f[i-1][j-s[i]* v[i]]+s[i]* w[i])\)，可以看到括号内的状态的背包容量是模 \(v[i]\) 同余的，那么根据余数我们可以划分出 \(v[i]\) 个组，据此，我们可以使用单调队列维护某个区间的最大值。
对于余数 \(r\)，有如下：
f[r] = f[r]
f[r + v] = max(f[r] + w, f[r + v])
f[r + 2 * v] = max(f[r] + 2 * w, f[r + v] + w, f[r + 2 * v])
...
可以看到每次更新，前面的值都会多 \(w\)，那么我们就需要变换一下，加同一个数不影响相对大小
f[r] = f[r]
f[r + v] = max(f[r], f[r + v] - w) + w
f[r + 2 * v] = max(f[r], f[r + v] - w, f[r + 2 * v] - 2 * w) + 2 * w
...
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[M], g[M];
int q[M];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d%d%d", &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])
{
if (hh <= tt && (j - q[hh]) / v[i] > s[i]) hh ++; // 剔除超出长度的元素
while (hh <= tt && g[q[tt]] - (q[tt] - r) / v[i] * w[i] <= g[j] - (j - r) / v[i] * w[i]) tt --;
q[++ tt] = j;
f[j] = max(f[j], g[q[hh]] + (j - q[hh]) / v[i] * w[i]);
}
}
}
printf("%d\n", f[m]);
return 0;
}