背包问题的一点看法-Toy模板网

这篇具有很好参考价值的文章主要介绍了背包问题的一点看法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

开篇

背包问题已经被人讲得很透彻了，上古大神写的《背包九讲》已经相当详细的阐述了背包问题，本文不会过多赘述，主要总结一些有关背包的有趣的玩意。

朴素的01背包/完全背包

01背包和完全背包是非常类似的问题，01背包的特点是每种物品最多只能取一个，而完全背包每种物品都可以任意取。
以下状态为前i种物品，背包容量为j的最大价值，volume是体积，value是价值。
01背包的状态转移方程。

$f [i] [j] = ma x (f [i - 1] [j], f [i - 1] [j - v o l [i]] + v a l [i])$

完全背包的状态转移方程.

$f [i] [j] = ma x (f [i - 1] [j], f [i] [j - v o l [i]] + v a l [i])$

首先， $f [i] [j]$ 关于i，j单调递增，考虑到物品种类数越多，就能填得越满；背包的容积越大就越能放下更多的物品。所以答案便是最后一个元素。
其次，考虑第i种物品的时候，选择不放的时候均是 $f [i - 1] [j]$ 相当于只考虑了前i-1种物品。
然后，如果考虑到再放一个物品的时候，01背包，的来源必须是前 $f [i - 1] [j - v o l [i]]$ ，因为01背包中每个物品最多只能取一次；而完全背包，可以在前i种的基础上继续考虑。
使用滚动数组的方法，我们可以优化空间复杂度，对于01背包我们使用倒序放入，如果我们把当前所在的体积称为游标，游标未遍历过的地方便是只考虑前i-1种的时候的最大价值；对于完全背包，我们使用正序，可以在考虑了前i种的基础上再次考虑第i种。
关于完全背包，体积为0的时候，可以是考虑前任意种的最大值。
一道01背包的简单题：传送门

int f[1005];//初始为0，可以看成考虑0种物品时候的最大价值
void solve() {
    int t, m;
    cin >> t >> m;
    for (int i = 0; i < m; i++) {//考虑放入所有物品
        int x, y;
        cin >> x >> y;
        for (int j = t; j >= x; j--) {//滚动
        //j左侧是未遍历过的，是不考虑当前物品的；右侧则是遍历过的
            f[j] = max(f[j], f[j - x] + y);
        }
    }
    cout << f[t] << '\n';
}

一道完全背包的简单题：传送门

const int N = 3005;
int f[1005];
void solve() {
    int n, v;
    cin >> n >> v;
    for (int i = 0; i < n; i++) {
        int vi, wi;
        cin >> vi >> wi;
        for (int j = vi; j <= v; j++) {//正着来
            f[j] = max(f[j], f[j - vi] + wi);
        }
    }
    cout << f[v] << '\n';
}

求方案数的“背包”/填满背包

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
上面的问题非常经典，类似的还有正整数拆分的问题（也可以用普通型生成函数来解决）等。
其实这可以看成一种背包问题，只不过，此时我们并不考虑这些物品的价值，我们在乎这些体积能否填满这个这个数（填满背包），在乎这些物品能够通过几种方式来填到这个体积。
求方案数：传送门

int climbStairs(int n){
    int *f = (int *)calloc(50, sizeof(int));
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    int ans = f[n];
    free(f);
    return ans;
}

我们考虑当前体积可以由那些体积加上一个物品转移而来，这里只有两个物品，1和2。
填满背包考虑的是一个数能否被其他的数给组合出来。
我们不需要考虑具体的方法数，我们只需要知道能否凑出某个数。（注意这点，这是bitset优化的基础，）
给定n种不同的物品，背包容量为V，求把背包填满的最大价值，如果无法填满输出-1
这是一种常见的问法，找不到板子题，就讲一下思路。
初始化背包容量为负无穷，然后f[0]=0，这个空的状态，是其他万千状态的源泉，再这个基础上，进行完全相同的01背包或者完全背包，最后检查一下f[V]是不是大于0，是则输出，不是则输出-1。
416. 分割等和子集 - 力扣（LeetCode）
分割成两个相等的子集只需要把全集的一半作为背包的容量，进行填满背包操作就行了。

两个问题是类似的，一个是求方案数，一个是是否存在。同样以f[0]为源头，开枝散叶，依据体积作为转移量，蔓生出一切状态。

背包求具体方案（从背包里取出）

如果说我们要求出抵达某状态的具体转移方案，我们只需要记录两个背包的状态是如何转移过来的。
我们再装背包的时候，是一个一个地尝试放入，使用了一些松弛的策略，经过复杂的状态变化得到最终的背包，而具体方案就比较简单，我们可以从背包里取出物品，看看是否能从这个状态回滚到上一个状态即可，因为这些物品取出的先后并不重要，我们只考虑是否能回滚，一个状态可能有多种回滚的方法，对于最后一个状态，可能有多个上一个状态转移到这个状态。
如果背包里有三个物品，大中小，我们可以先去出大的，也可以先取出中等的，也可以先取出小的，这都是可以的，因为取完之后，这些状态的前驱都是存在的，我们可以一直取出某个物品来回滚到最初的状态。
背包九讲之 01背包问题求具体方案_yam bean的博客-CSDN博客

花招

bitset优化

前面说了，bitset优化是不考虑方案数，只考虑能否达到的情况，特别是在填满背包中。
bitset相关：
- 声明bitset bt或 bitset bt(“10010”) 导入字符串或者导入无符号数，位数不足补前导零。
- bitset类型支持位运算，支持下标运算
- 位运算时间复杂度少32倍

    //初始可抵达的容量为0
    bitset<V> bt(1);//00000000001->f[0] = 1
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        bt |= bt << v;
    }

根号分治（限制和背包）

物品数目未知的情况下，例如考虑一种正整数拆分，如果说每种物品的大小均不相同，那么这些物品的总数不超过 $\sqrt{n}$
等差数列求和可以知道。
1 + 2 + 3 + 4 + 5… = n
最多不超过 $\sqrt{n}$ 项

二进制优化(多重背包)

如果说01背包有许多元素的值相同那么就可以称为多重背包。
例如n个元素和为n，的背包，如果是普通01背包，我们需要 $O(n^2)$ ，如果每个元素都相同，通过二进制打包我们可以优化到 $O(n\log{n})$
二进制优化的方法是，将若干相同大小的物品，拆解成2的幂，多余的单独成组。
例如10 = 1 + 2 + 4 + 3
为什么可以这样分呢？
- 首先这些数和原先的数的可组合的范围是一样的（原来10个物品在最终答案的背包内的状态数目范围是0~10，这些2的，幂可以组合到所有 2的最大幂 * 2 - 1的所有数，二进制形式可知，如果大于这个数小于原数，此时，我们需要从原数中减去此时的数，例如 8 我们只需凑出 2 ，取2以外所有的小组即可。）
- 这样分会减小方法数。但是不改变能否抵达的真假性。例如打包成上述之后，4的合成方法只有3+1和4和原本可以是 1 + 1 + 1 + 1, 2 + 2, 2 + 1 + 1，3 + 1, 4。但是由于可组合的性不变，打包之后仍然能够抵达这个状态。

一道花招题

ICPC江西省赛H题
Problem - H - Codeforces
Tutorial说得可能有点模糊，稍微解释一下，就是当前最大值，到下一个更大值出现前都是属于同一组的，新的最大值以及后续管辖的较小值也是属于同一组的，不过可能是本组也可能是对面组，先划分成组，对这些元素进行背包即可，看看能否平分就行。
这是限制和的背包，考虑两个极端，大量重复是 $O(n\log{n})$ ，均不重复是 $O(n\sqrt{n})$ ，由于bitset优化所以最坏复杂度是 $O(n\sqrt{n}/w)$

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
bitset<N> bt;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int p = 0, mx = a[0];
    vector<int> items;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > mx) {
            mx = a[i];
            items.push_back(i - p);
            p = i;
        }
    }
    items.push_back(n - p);

    bt.reset();
    map<int, int> mp;
    for (auto x : items) {
        mp[x]++;
    }
    
    vector<int> pkg;
    for (auto i : mp) {
        int cnt = i.second;
        int val = i.first;
        int now = 1;
        while (cnt >= now) {
            pkg.push_back(now * val);
            cnt -= now;
            now *= 2;
        }
        if (cnt) pkg.push_back(cnt * val);
    }

    bt[0] = 1;
    for (auto x : pkg) {
        bt |= bt << x;
    }

    cout << (bt[n / 2] ? "Yes\n" : "No\n");
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}