DDOSvoid's Blog

背包

发表于 更新于 分类于
本文字数： 826 阅读时长 ≈ 1 分钟

简介

$RT$

01背包

题目概述

有 $n$ 个物品和一个容量为 $v$ 的背包，放入第 $i$ 件物品耗费的容量为 $w_i$，得到的价值是 $c_i$，求将哪些物品放入背包使得价值最大

solution

我们令 $f[i][j]$ 表示放了前 $i$ 种物品，占了小于等于 $i$ 体积的最大价值

$dp$ 时可以优化掉第一维，需要注意第二维并不是精确的值，而是”继承”了前面的值

复杂度 $O(nm)$

1
2
3
for (int i = 1; i <= n; ++i)
    for (int j = m; j >= w[i]; --j)
        f[j] = max(f[j], f[j - w[i]] + c[i]);

完全背包

题目概述

每个物品可以用无限次

solution

只需要改变第二层循环的顺序即可

复杂度 $O(nm)$

1
2
3
4
for (int i = 1; i <= n; ++i)
    for (int j = w[i]; j <= m; ++j)
        f[j] = max(f[j], f[j - w[i]] + c[i]);

多重背包

题目概述

第 $i$ 种物品可以用 $p[i]$ 次

solution

朴素的做法是多循环 $p[i]$ 次，复杂度多乘一个 $p[i]$

优化是将 $p[i]$ 二进制拆分成多个物品，复杂度 $O(nmlogp)$

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 1; i <= n; ++i) {
        int p, _w, _c; cin >> _c >> _w >> p; 
        for (int j = 1; j <= p; j <<= 1) {
            w[++c1] = _w * j;
            c[c1] = _c * j;
            p -= j; 
        }
        if (p) w[++c1] = _w * p, c[c1] = _c * p;
    } 
    for (int i = 1; i <= c1; ++i)
        for (int j = m; j >= w[i]; --j)
            f[j] = max(f[j], f[j - w[i]] + c[i]);
    cout << f[m] << endl;

还可以进一步优化，利用单调队列，复杂度为 $O()$