WillHou's Blog
0%

【题解】巨大 01 背包问题

发表于 分类于 Valine：
巨大的约束条件的 01 背包！

题目描述与 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;
}