题解AT_arc073_b
shaozhehan
·
·
题解
原题链接
AtCoder 链接
题目大意：
有 N 个物品（1\leq N\leq 100），第 i 个物品重 w_i 千克（1\leq w_i\leq 10^9、w_1\leq w_i\leq w_1+3），有 v_i 元的价值。现有一个最大容量为 W 的背包，即最多装 W 千克的物品。问：这个背包能装的最大价值是多少？
思路：
乍一看，这就是一道简单的 01 背包，但是 1\leq w_i\leq 10^9 导致我们不能用普通的 01 背包解决方法来解决此题。
但是，我们看到题目中有一个特殊的数据范围：w_1\leq w_i\leq w_1+3。它有什么用呢？
我们可以发现，对于任意的 2\leq i\leq N，w_i-w_1\leq 3，我们可以把每一个 w_i 都减掉 w_1，这样就不会 MLE 了。
状态表示：
这里我们看一下 $i$、$j$、$k$ 的取值范围：
显然，$1\leq i\leq n$，$0\leq k\leq i$。因为 $w$ 数组已经偏移，所以 $w_i\leq 3$。因此，$0\leq j\leq 3i$。
状态转移方程：
考虑 $dp_{i,j,k}$ 的值。
- 如果第 $i$ 个物品不选，那么 $dp_{i,j,k}=dp_{i-1,j,k}$。
- 如果 $j\geq w_i$，那么还有一种情况：第 $i$ 个物品选了，$dp_{i,j,k}=dp_{i-1,j-w_i,k}+v_i$。
综上，我们可以推出状态转移方程：$dp_{i,j,k}=\begin{cases}dp_{i-1,j-1,k-1},&j<w_i\\\min\{dp_{i-1,j,k},dp_{i-1,j-w_i,k}+v_i\},&\text{otherwise}\end{cases}$。
答案就是所有 $i=n$ 且 $j+kw_1\leq W$ 的 $dp_{i,j,k}$ 的最大值。
此算法时间复杂度为 $\operatorname{O}(n^3)$。
坑点：
1. 全程开 ```long long```，否则会炸精度！
1. 最后求答案的时候千万不要忘记 $j+kw_1\leq W$ 的特判！
1. 记得把 $w_1$ 存储起来，以便后面数值偏移和上面提到的特判！
上代码：
```cpp
#include <iostream>
using namespace std;
long long w[101], v[101], dp[101][301][101];
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);// cin、cout 加速
long long n, W, w_1;// 坑点 3：记得把 w[1] 存储起来
cin >> n >> W >> w_1 >> v[1];
for (int i = 2; i <= n; i++){
cin >> w[i] >> v[i];
w[i] -= w_1;// 数值偏移
}
for (int i = 1; i <= n; i++){
for (int k = 1; k <= i; k++){
for (int j = 0; j <= 3 * i; j++){
// 状态转移方程
if (j < w[i]){
dp[i][j][k] = dp[i - 1][j][k];
} else {
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - w[i]][k - 1] + v[i]);
}
}
}
}
// 求答案
long long ans = -1;
for (int j = 0; j <= 3 * n; j++){
for (int k = 0; k <= n; k++){
if (j + k * w_1 <= W){// 坑点 2：特判要注意
ans = max(ans, dp[n][j][k]);
}
}
}
cout << ans << "\n";
return 0;
}
```