题目描述与 01 背包一模一样。不一样的地方在数据范围:
\(n(物品数量)\leq 100, W(重量约束)\leq10^9,
w[i](第 i 件物品重量)\leq 10^9, v[i](第 i 件物品价值)\leq
1000\)
发现:约束条件的数据范围非常大,所以无法使用常规的 01
背包模板解决,会造成
MLE。考虑这个问题的时候,可以从数据范围中获得提示。虽然约束条件的数据范围大,但是物品数量非常少。所以,可以考虑将目标与约束互换,即:
传统 01 背包 |
最大化总价值 |
总重量 \(\leq W\) |
巨大 01 背包 |
最小化总重量 |
总价值 \(\geq V\) |
经过这样的转化后,能够想到两种定义状态的方法。
f[i][j]
表示只考虑前 \(i\) 件物品能装下至少价值为 \(p\) 的包最小载重是多少;
f[i][j]
表示只考虑前 \(i\) 件物品能装下恰好价值为 \(p\) 的包最小载重是多少。
下面对这两种 DP 分别讨论。
解法 A
两种情况: \[
\begin{cases}
f[i][j]=min(f[i-1][p],w[i]), v[i]>p(单个物品就能完成) \\
f[i][j]=min(f[i-1][p], f[i-1][j-v[i]]+w[i]), else
\end{cases}
\] 故代码为:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include <iostream> typedef long long LL; const LL N = 109; const LL MV = 1e5 + 9; const LL INF = 0x3F3F3F3F3F3F3F3F; LL n, W, V, w[N], v[N], f[N][MV]; int main() { scanf("%lld%lld", &n, &W); for (LL i = 1; i <= n; i++) scanf("%lld%lld", w + i, v + i); V = n * 1000; for (LL i = 1; i <= V; i++) f[0][i] = INF; for (LL i = 1; i <= n; i++) for (LL j = 0; j <= V; j++) if (v[i] > j) f[i][j] = std::min(f[i-1][j], w[i]); else f[i][j] = std::min(f[i-1][j], f[i-1][j-v[i]] + w[i]); for (int i = V; i >= 0; i--) if (f[n][i] <= W) { printf("%d", p); return 0; } return 0; }
|
解法 B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include <iostream> typedef long long LL; const LL N = 109; const LL MV = 1e5 + 9; const LL INF = 0x3F3F3F3F3F3F3F3F; LL n, W, V, w[N], v[N], f[N][MV]; int main() { scanf("%lld%lld", &n, &W); for (LL i = 1; i <= n; i++) scanf("%lld%lld", w + i, v + i); V = n * 1000; for (LL i = 1; i <= V; i++) f[0][i] = INF; for (LL i = 1; i <= n; i++) for (LL j = 0; j <= V; j++) if (v[i] > j) f[i][j] = f[i-1][j]; else f[i][j] = std::min(f[i-1][j], f[i-1][j-v[i]] + w[i]); for (LL i = V; i >= 0; i--) if (f[n][i] <= W) { printf("%d", i); return 0; } return 0; }
|